From 59312b19a62dbeb8012f1de8856318d31fb1eef5 Mon Sep 17 00:00:00 2001 From: Owen Anderson Date: Mon, 28 Aug 2006 02:09:46 +0000 Subject: [PATCH] Make LoopUnroll fold excessive BasicBlocks. This results in a significant speedup of gccas on 252.eon git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@29936 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/LoopUnroll.cpp | 98 +++++++++++++++++++++++++--- 1 file changed, 89 insertions(+), 9 deletions(-) diff --git a/lib/Transforms/Scalar/LoopUnroll.cpp b/lib/Transforms/Scalar/LoopUnroll.cpp index c1a510dcb5e..3bff2737bcd 100644 --- a/lib/Transforms/Scalar/LoopUnroll.cpp +++ b/lib/Transforms/Scalar/LoopUnroll.cpp @@ -25,6 +25,7 @@ #include "llvm/Analysis/LoopInfo.h" #include "llvm/Transforms/Utils/Cloning.h" #include "llvm/Transforms/Utils/Local.h" +#include "llvm/Support/CFG.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/ADT/Statistic.h" @@ -48,6 +49,7 @@ namespace { public: virtual bool runOnFunction(Function &F); bool visitLoop(Loop *L); + BasicBlock* FoldBlockIntoPredecessor(BasicBlock* BB); /// This transformation requires natural loop information & requires that /// loop preheaders be inserted into the CFG... @@ -118,6 +120,76 @@ static inline void RemapInstruction(Instruction *I, } } +// FoldBlockIntoPredecessor - Folds a basic block into its predecessor if it +// only has one predecessor, and that predecessor only has one successor. +// Returns the new combined block. +BasicBlock* LoopUnroll::FoldBlockIntoPredecessor(BasicBlock* BB) { + // Merge basic blocks into their predecessor if there is only one distinct + // pred, and if there is only one distinct successor of the predecessor, and + // if there are no PHI nodes. + // + pred_iterator PI(pred_begin(BB)), PE(pred_end(BB)); + BasicBlock *OnlyPred = *PI++; + for (; PI != PE; ++PI) // Search all predecessors, see if they are all same + if (*PI != OnlyPred) { + OnlyPred = 0; // There are multiple different predecessors... + break; + } + + BasicBlock *OnlySucc = 0; + if (OnlyPred && OnlyPred != BB && // Don't break self loops + OnlyPred->getTerminator()->getOpcode() != Instruction::Invoke) { + // Check to see if there is only one distinct successor... + succ_iterator SI(succ_begin(OnlyPred)), SE(succ_end(OnlyPred)); + OnlySucc = BB; + for (; SI != SE; ++SI) + if (*SI != OnlySucc) { + OnlySucc = 0; // There are multiple distinct successors! + break; + } + } + + if (OnlySucc) { + DEBUG(std::cerr << "Merging: " << *BB << "into: " << *OnlyPred); + TerminatorInst *Term = OnlyPred->getTerminator(); + + // Resolve any PHI nodes at the start of the block. They are all + // guaranteed to have exactly one entry if they exist, unless there are + // multiple duplicate (but guaranteed to be equal) entries for the + // incoming edges. This occurs when there are multiple edges from + // OnlyPred to OnlySucc. + // + while (PHINode *PN = dyn_cast(&BB->front())) { + PN->replaceAllUsesWith(PN->getIncomingValue(0)); + BB->getInstList().pop_front(); // Delete the phi node... + } + + // Delete the unconditional branch from the predecessor... + OnlyPred->getInstList().pop_back(); + + // Move all definitions in the successor to the predecessor... + OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList()); + + // Make all PHI nodes that referred to BB now refer to Pred as their + // source... + BB->replaceAllUsesWith(OnlyPred); + + std::string OldName = BB->getName(); + + // Erase basic block from the function... + LI->removeBlock(BB); + BB->eraseFromParent(); + + // Inherit predecessors name if it exists... + if (!OldName.empty() && !OnlyPred->hasName()) + OnlyPred->setName(OldName); + + return OnlyPred; + } + + return 0; +} + bool LoopUnroll::visitLoop(Loop *L) { bool Changed = false; @@ -247,13 +319,7 @@ bool LoopUnroll::visitLoop(Loop *L) { RemapInstruction(I, LastValueMap); } - // Insert the branches that link the different iterations together - for (unsigned i = 0; i < Latches.size()-1; ++i) - new BranchInst(Headers[i+1], Latches[i]); - // Finally, add an unconditional branch to the block to continue into the exit - // block. - new BranchInst(LoopExit, Latches[Latches.size()-1]); // Update PHI nodes that reference the final latch block if (TripCount > 1) { @@ -281,14 +347,28 @@ bool LoopUnroll::visitLoop(Loop *L) { PHINode *PN = OrigPHINode[i]; PN->replaceAllUsesWith(PN->getIncomingValueForBlock(Preheader)); Header->getInstList().erase(PN); - } - + } + + // Insert the branches that link the different iterations together + for (unsigned i = 0; i < Latches.size()-1; ++i) { + new BranchInst(Headers[i+1], Latches[i]); + if(BasicBlock* Fold = FoldBlockIntoPredecessor(Headers[i+1])) { + std::replace(Latches.begin(), Latches.end(), Headers[i+1], Fold); + std::replace(Headers.begin(), Headers.end(), Headers[i+1], Fold); + } + } + + // Finally, add an unconditional branch to the block to continue into the exit + // block. + new BranchInst(LoopExit, Latches[Latches.size()-1]); + FoldBlockIntoPredecessor(LoopExit); + // At this point, the code is well formed. We now do a quick sweep over the // inserted code, doing constant propagation and dead code elimination as we // go. const std::vector &NewLoopBlocks = L->getBlocks(); for (std::vector::const_iterator BB = NewLoopBlocks.begin(), - E = NewLoopBlocks.end(); BB != E; ++BB) + BBE = NewLoopBlocks.end(); BB != BBE; ++BB) for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); I != E; ) { Instruction *Inst = I++; -- 2.34.1