Changes in directory llvm/lib/Transforms/Scalar:
LoopUnroll.cpp updated: 1.26 -> 1.27
---
Log message:
Make LoopUnroll fold excessive BasicBlocks. This results in a significant
speedup of
gccas on 252.eon
---
Diffs of the changes: (+89 -9)
LoopUnroll.cpp | 98 +++++++++++++++++++++++++++++++++++++++++++++++++++------
1 files changed, 89 insertions(+), 9 deletions(-)
Index: llvm/lib/Transforms/Scalar/LoopUnroll.cpp
diff -u llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.26
llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.27
--- llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.26 Sun Aug 27 17:42:52 2006
+++ llvm/lib/Transforms/Scalar/LoopUnroll.cpp Sun Aug 27 21:09:46 2006
@@ -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 @@
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 @@
}
}
+// 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<PHINode>(&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 @@
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 @@
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<BasicBlock*> &NewLoopBlocks = L->getBlocks();
for (std::vector<BasicBlock*>::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++;
_______________________________________________
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
