Index: lib/Transforms/IPO/PartialInlining.cpp =================================================================== --- lib/Transforms/IPO/PartialInlining.cpp +++ lib/Transforms/IPO/PartialInlining.cpp @@ -37,7 +37,18 @@ bool run(Module &M); Function *unswitchFunction(Function *F); + // Finds a ghain of blocks (starting from function entry) + // that guards a return block. Returns the ReturnBlock and NonReturnBlock. + std::tuple findEntryBlocks(Function *F); + private: + // A chain of basic blocks starting from the function entry point. + // Except for the function entry block, each block in the chain + // has the previous block in the vector as its single predecessor and + // all the blocks in the chain have a common non return block + // as their successor. The last block in the chain also has the return + // block as its successor. + std::vector Entries; InlineFunctionInfo IFI; }; struct PartialInlinerLegacyPass : public ModulePass { @@ -64,34 +75,131 @@ }; } -Function *PartialInlinerImpl::unswitchFunction(Function *F) { - // First, verify that this function is an unswitching candidate... +std::tuple +PartialInlinerImpl::findEntryBlocks(Function *F) { BasicBlock *EntryBlock = &F->front(); BranchInst *BR = dyn_cast(EntryBlock->getTerminator()); if (!BR || BR->isUnconditional()) - return nullptr; + return std::make_tuple(nullptr, nullptr); BasicBlock *ReturnBlock = nullptr; BasicBlock *NonReturnBlock = nullptr; unsigned ReturnCount = 0; + for (BasicBlock *BB : successors(EntryBlock)) { if (isa(BB->getTerminator())) { ReturnBlock = BB; ReturnCount++; - } else + } else { NonReturnBlock = BB; + } + } + + if (ReturnCount == 1) { + Entries.push_back(EntryBlock); + return std::make_tuple(ReturnBlock, NonReturnBlock); + } else if (ReturnCount != 0) { + return std::make_tuple(nullptr, nullptr); + } + + // Handle more complicated case where the ReturnBlock is guarded by + // a chain of predicates: + // First find the return block: + NonReturnBlock = nullptr; + + for (auto &BB : *F) { + TerminatorInst *TI = BB.getTerminator(); + if (isa(TI)) { + ReturnBlock = &BB; + ReturnCount++; + } } if (ReturnCount != 1) + return std::make_tuple(nullptr, nullptr); + + // Returns true if Succ is BB's successor + auto IsSuccessor = [](BasicBlock *Succ, BasicBlock *BB) { + return is_contained(successors(BB), Succ); + }; + + if (succ_end(EntryBlock) - succ_begin(EntryBlock) == 2) { + BasicBlock *Succ1 = *succ_begin(EntryBlock); + BasicBlock *Succ2 = *(succ_begin(EntryBlock) + 1); + if (IsSuccessor(Succ1, Succ2)) + NonReturnBlock = Succ1; + else if (IsSuccessor(Succ2, Succ1)) + NonReturnBlock = Succ2; + } + + if (!NonReturnBlock) + return std::make_tuple(nullptr, nullptr); + + // Now walk backward from the return block to find the last block in the + // entry chain: + BasicBlock *LastEntryInChain = nullptr; + for (BasicBlock *BB : predecessors(ReturnBlock)) { + // Find a predecessor that has NonReturnBlock as its + // successor: + if (IsSuccessor(NonReturnBlock, BB)) { + // found more than one, bail .. + if (LastEntryInChain) { + LastEntryInChain = nullptr; + break; + } else { + LastEntryInChain = BB; + } + } + } + + if (LastEntryInChain == nullptr) + return std::make_tuple(nullptr, nullptr); + + // Now walk up the chain till the function entry is reached: + BasicBlock *CurrEntryInChain = LastEntryInChain; + do { + Entries.push_back(CurrEntryInChain); + if (CurrEntryInChain == EntryBlock) + break; + + CurrEntryInChain = CurrEntryInChain->getSinglePredecessor(); + } while (CurrEntryInChain && IsSuccessor(NonReturnBlock, CurrEntryInChain)); + + if (CurrEntryInChain != EntryBlock) + return std::make_tuple(nullptr, nullptr); + + std::reverse(Entries.begin(), Entries.end()); + return std::make_tuple(ReturnBlock, NonReturnBlock); +} + +Function *PartialInlinerImpl::unswitchFunction(Function *F) { + + BasicBlock *ReturnBlock = nullptr; + BasicBlock *NonReturnBlock = nullptr; + + std::tie(ReturnBlock, NonReturnBlock) = findEntryBlocks(F); + + if (!ReturnBlock) return nullptr; +#ifndef NDEBUG + BasicBlock *EntryBlock = Entries[0]; + assert(EntryBlock && EntryBlock == &F->front()); + assert(NonReturnBlock); +#endif + // 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(VMap[EntryBlock]); + // Last block in the entry chain: + BasicBlock *NewLastEntryBlock = cast(VMap[&*Entries.back()]); BasicBlock *NewReturnBlock = cast(VMap[ReturnBlock]); BasicBlock *NewNonReturnBlock = cast(VMap[NonReturnBlock]); + DenseSet NewEntryChains; + for (BasicBlock *BB : Entries) { + NewEntryChains.insert(cast(VMap[BB])); + } // Go ahead and update all uses to the duplicate, so that we can just // use the inliner functionality when we're done hacking. @@ -116,20 +224,28 @@ Ins = NewReturnBlock->getFirstNonPHI(); RetPhi->addIncoming(&*I, PreReturn); - RetPhi->addIncoming(OldPhi->getIncomingValueForBlock(NewEntryBlock), - NewEntryBlock); - OldPhi->removeIncomingValue(NewEntryBlock); + RetPhi->addIncoming(OldPhi->getIncomingValueForBlock(NewLastEntryBlock), + NewLastEntryBlock); + OldPhi->removeIncomingValue(NewLastEntryBlock); ++I; } - NewEntryBlock->getTerminator()->replaceUsesOfWith(PreReturn, NewReturnBlock); + NewLastEntryBlock->getTerminator()->replaceUsesOfWith(PreReturn, + NewReturnBlock); + // Returns true if the block is to be partial inlined into the caller + // (i.e. not to be extracted to the out of line function) + auto ToBeInlined = [=](BasicBlock *BB) { + if (BB == NewReturnBlock || NewEntryChains.count(BB)) + return true; + return false; + + }; // Gather up the blocks that we're going to extract. std::vector ToExtract; ToExtract.push_back(NewNonReturnBlock); for (BasicBlock &BB : *DuplicateFunction) - if (&BB != NewEntryBlock && &BB != NewReturnBlock && - &BB != NewNonReturnBlock) + if (!ToBeInlined(&BB) && &BB != NewNonReturnBlock) ToExtract.push_back(&BB); // The CodeExtractor needs a dominator tree. Index: test/Transforms/CodeExtractor/MultiConditions.ll =================================================================== --- test/Transforms/CodeExtractor/MultiConditions.ll +++ test/Transforms/CodeExtractor/MultiConditions.ll @@ -0,0 +1,48 @@ +; RUN: opt < %s -partial-inliner -S | FileCheck %s +; RUN: opt < %s -passes=partial-inliner -S | FileCheck %s + +define i32 @bar(i32) local_unnamed_addr #0 { + %2 = icmp slt i32 %0, 0 + br i1 %2, label %6, label %3 + +;