Index: /Users/rriddle/Desktop/llvm/llvm/include/llvm/Transforms/Utils/CodeExtractor.h =================================================================== --- /Users/rriddle/Desktop/llvm/llvm/include/llvm/Transforms/Utils/CodeExtractor.h +++ /Users/rriddle/Desktop/llvm/llvm/include/llvm/Transforms/Utils/CodeExtractor.h @@ -47,6 +47,7 @@ // Various bits of state computed on construction. DominatorTree *const DT; const bool AggregateArgs; + const bool ExtractDominatedAllocas; // Bits of intermediate state computed at various phases of extraction. SetVector Blocks; @@ -58,7 +59,8 @@ /// /// In this formation, we don't require a dominator tree. The given basic /// block is set up for extraction. - CodeExtractor(BasicBlock *BB, bool AggregateArgs = false); + CodeExtractor(BasicBlock *BB, bool AggregateArgs = false, + bool ExtractDominatingAllocas = false); /// \brief Create a code extractor for a sequence of blocks. /// @@ -67,20 +69,23 @@ /// sequence out into its new function. When a DominatorTree is also given, /// extra checking and transformations are enabled. CodeExtractor(ArrayRef BBs, DominatorTree *DT = nullptr, - bool AggregateArgs = false); + bool AggregateArgs = false, + bool ExtractDominatingAllocas = false); /// \brief Create a code extractor for a loop body. /// /// Behaves just like the generic code sequence constructor, but uses the /// block sequence of the loop. - CodeExtractor(DominatorTree &DT, Loop &L, bool AggregateArgs = false); + CodeExtractor(DominatorTree &DT, Loop &L, bool AggregateArgs = false, + bool ExtractDominatingAllocas = false); /// \brief Create a code extractor for a region node. /// /// Behaves just like the generic code sequence constructor, but uses the /// block sequence of the region node passed in. CodeExtractor(DominatorTree &DT, const RegionNode &RN, - bool AggregateArgs = false); + bool AggregateArgs = false, + bool ExtractDominatingAllocas = false); /// \brief Perform the extraction, returning the new function. /// 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 @@ -29,22 +29,22 @@ STATISTIC(NumPartialInlined, "Number of functions partially inlined"); namespace { -struct PartialInlinerLegacyPass : public ModulePass { - static char ID; // Pass identification, replacement for typeid - PartialInlinerLegacyPass() : ModulePass(ID) { - initializePartialInlinerLegacyPassPass(*PassRegistry::getPassRegistry()); - } + struct PartialInlinerLegacyPass : public ModulePass { + static char ID; // Pass identification, replacement for typeid + PartialInlinerLegacyPass() : ModulePass(ID) { + initializePartialInlinerLegacyPassPass(*PassRegistry::getPassRegistry()); + } - bool runOnModule(Module &M) override { - if (skipModule(M)) - return false; - ModuleAnalysisManager DummyMAM; - auto PA = Impl.run(M, DummyMAM); - return !PA.areAllPreserved(); - } + bool runOnModule(Module &M) override { + if (skipModule(M)) + return false; + ModuleAnalysisManager DummyMAM; + auto PA = Impl.run(M, DummyMAM); + return !PA.areAllPreserved(); + } -private: - PartialInlinerPass Impl; + private: + PartialInlinerPass Impl; }; } @@ -62,7 +62,7 @@ BranchInst *BR = dyn_cast(entryBlock->getTerminator()); if (!BR || BR->isUnconditional()) return nullptr; - + BasicBlock* returnBlock = nullptr; BasicBlock* nonReturnBlock = nullptr; unsigned returnCount = 0; @@ -73,10 +73,10 @@ } 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); @@ -84,11 +84,11 @@ 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 @@ -110,11 +110,11 @@ 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); @@ -129,10 +129,10 @@ // Extract the body of the if. Function* extractedFunction - = CodeExtractor(toExtract, &DT).extractCodeRegion(); - + = CodeExtractor(toExtract, &DT, false, true).extractCodeRegion(); + InlineFunctionInfo IFI; - + // Inline the top-level if test into all callers. std::vector Users(duplicateFunction->user_begin(), duplicateFunction->user_end()); @@ -141,14 +141,14 @@ 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; } @@ -163,27 +163,27 @@ 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 (I->getParent()->getParent() == currFunc) { + recursive = true; + break; + } if (recursive) continue; - - + + if (Function* newFunc = unswitchFunction(currFunc)) { worklist.push_back(newFunc); changed = true; } - + } if (changed) return PreservedAnalyses::none(); return PreservedAnalyses::all(); -} +} \ No newline at end of file Index: /Users/rriddle/Desktop/llvm/llvm/lib/Transforms/Utils/CodeExtractor.cpp =================================================================== --- /Users/rriddle/Desktop/llvm/llvm/lib/Transforms/Utils/CodeExtractor.cpp +++ /Users/rriddle/Desktop/llvm/llvm/lib/Transforms/Utils/CodeExtractor.cpp @@ -119,22 +119,30 @@ return buildExtractionBlockSet(R.block_begin(), R.block_end()); } -CodeExtractor::CodeExtractor(BasicBlock *BB, bool AggregateArgs) +CodeExtractor::CodeExtractor(BasicBlock *BB, bool AggregateArgs, + bool ExtractDominatingAllocas) : DT(nullptr), AggregateArgs(AggregateArgs||AggregateArgsOpt), + ExtractDominatedAllocas(ExtractDominatingAllocas), Blocks(buildExtractionBlockSet(BB)), NumExitBlocks(~0U) {} CodeExtractor::CodeExtractor(ArrayRef BBs, DominatorTree *DT, - bool AggregateArgs) + bool AggregateArgs, + bool ExtractDominatingAllocas) : DT(DT), AggregateArgs(AggregateArgs||AggregateArgsOpt), + ExtractDominatedAllocas(ExtractDominatingAllocas), Blocks(buildExtractionBlockSet(BBs)), NumExitBlocks(~0U) {} -CodeExtractor::CodeExtractor(DominatorTree &DT, Loop &L, bool AggregateArgs) +CodeExtractor::CodeExtractor(DominatorTree &DT, Loop &L, bool AggregateArgs, + bool ExtractDominatingAllocas) : DT(&DT), AggregateArgs(AggregateArgs||AggregateArgsOpt), + ExtractDominatedAllocas(ExtractDominatingAllocas), Blocks(buildExtractionBlockSet(L.getBlocks())), NumExitBlocks(~0U) {} CodeExtractor::CodeExtractor(DominatorTree &DT, const RegionNode &RN, - bool AggregateArgs) + bool AggregateArgs, + bool ExtractDominatingAllocas) : DT(&DT), AggregateArgs(AggregateArgs||AggregateArgsOpt), + ExtractDominatedAllocas(ExtractDominatingAllocas), Blocks(buildExtractionBlockSet(RN)), NumExitBlocks(~0U) {} /// definedInRegion - Return true if the specified value is defined in the @@ -157,6 +165,17 @@ return false; } +/// hasOutsideUses - Return true if the specified instruction is used outside of +/// the region that is being extracted. +static bool hasOutsideUses(const SetVector &Blocks, Instruction *I){ + for(Use &U : I->uses()) { + Instruction *User = dyn_cast(U.getUser()); + if(User && !Blocks.count(User->getParent())) + return true; + } + return false; +} + void CodeExtractor::findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs) const { for (BasicBlock *BB : Blocks) { @@ -705,6 +724,19 @@ // Find inputs to, outputs from the code region. findInputsOutputs(inputs, outputs); + // If we are extracting the dominated allocas then we need to remove them + // from the inputs. + if(ExtractDominatedAllocas) + for(unsigned long I = 0, E = inputs.size(); I < E; ++I){ + // Only take static allocas. + AllocaInst *AI = const_cast(dyn_cast(inputs[I])); + if (AI && AI->isStaticAlloca() && !hasOutsideUses(Blocks, AI)) { + AI->moveBefore(&newFuncRoot->front()); + inputs.remove(AI); + --I; --E; + } + } + SmallPtrSet ExitBlocks; for (BasicBlock *Block : Blocks) for (succ_iterator SI = succ_begin(Block), SE = succ_end(Block); SI != SE; Index: /Users/rriddle/Desktop/llvm/llvm/test/Transforms/CodeExtractor/2016-07-20-ExtractDominatedStaticAllocas.ll =================================================================== --- /Users/rriddle/Desktop/llvm/llvm/test/Transforms/CodeExtractor/2016-07-20-ExtractDominatedStaticAllocas.ll +++ /Users/rriddle/Desktop/llvm/llvm/test/Transforms/CodeExtractor/2016-07-20-ExtractDominatedStaticAllocas.ll @@ -0,0 +1,25 @@ +; RUN: opt < %s -partial-inliner -S | FileCheck %s +; This testcase hoists a dominated static alloca + +define internal i32 @inlinedFunc(i1) { +entry: + %dominated.alloca = alloca i32, align 4 + br i1 %0, label %if.then, label %return +if.then: +; Dummy store to represent the only use + store i32 10, i32* %dominated.alloca, align 4 + br label %return +return: ; preds = %entry + ret i32 0 +} + +define internal i32 @dummyCaller(i1) { +entry: + %val = call i32 @inlinedFunc(i1 %0) + ret i32 %val +} + +; CHECK-LABEL: @inlinedFunc.1_if.then +; CHECK: alloca i32 + +