Allow loop-idiom to run on multiple BB loops, but still only scan the loop

header for now for memset/memcpy opportunities.  It turns out that loop-rotate
is successfully rotating loops, but *DOESN'T MERGE THE BLOCKS*, turning "for 
loops" into 2 basic block loops that loop-idiom was ignoring.

With this fix, we form many *many* more memcpy and memsets than before, including
on the "history" loops in the viterbi benchmark, which look like this:

        for (j=0; j<MAX_history; ++j) {
          history_new[i][j+1] = history[2*i][j];
        }

Transforming these loops into memcpy's speeds up the viterbi benchmark from
11.98s to 3.55s on my machine.  Woo.

llvm-svn: 122685

1 files changed, 5 insertions, 5 deletions

diff --git a/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp b/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
index e9394cd5c02..84e33f062b0 100644
--- a/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
+++ b/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
@@ -126,11 +126,6 @@ static void DeleteDeadInstruction(Instruction *I, ScalarEvolution &SE) {
 bool LoopIdiomRecognize::runOnLoop(Loop *L, LPPassManager &LPM) {
   CurLoop = L;
   
-  // We only look at trivial single basic block loops.
-  // TODO: eventually support more complex loops, scanning the header.
-  if (L->getBlocks().size() != 1)
-    return false;
-  
   // The trip count of the loop must be analyzable.
   SE = &getAnalysis<ScalarEvolution>();
   if (!SE->hasLoopInvariantBackedgeTakenCount(L))
@@ -142,6 +137,11 @@ bool LoopIdiomRecognize::runOnLoop(Loop *L, LPPassManager &LPM) {
   TD = getAnalysisIfAvailable<TargetData>();
   if (TD == 0) return false;
   
+  // TODO: We currently only scan the header of the loop, because it is the only
+  // part that is known to execute and we don't want to make a conditional store
+  // into an unconditional one in the preheader.  However, there can be diamonds
+  // and other things in the loop that would make other blocks "always executed"
+  // we should get the full set and scan each block.
   BasicBlock *BB = L->getHeader();
   DEBUG(dbgs() << "loop-idiom Scanning: F[" << BB->getParent()->getName()
                << "] Loop %" << BB->getName() << "\n");