Avoid duplicating loop header which leads to unnatural loops (and just seem like...

Patch by Florian Brandner.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52223 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/lib/Transforms/Scalar/TailDuplication.cpp b/lib/Transforms/Scalar/TailDuplication.cpp
index d0998ab5a65d5984d7443985da79f179aa60e357..4e0949a2b4712c4cd9e17bf27e30f8faffe0c6d3 100644 (file)
--- a/lib/Transforms/Scalar/TailDuplication.cpp
+++ b/lib/Transforms/Scalar/TailDuplication.cpp
@@ -33,6 +33,7 @@
 #include "llvm/Support/Debug.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/Analysis/LoopInfo.h"
 #include <map>
 using namespace llvm;
 
@@ -50,10 +51,12 @@ namespace {
     static char ID; // Pass identification, replacement for typeid
     TailDup() : FunctionPass((intptr_t)&ID) {}
 
+    virtual void getAnalysisUsage(AnalysisUsage &AU) const;
   private:
     inline bool shouldEliminateUnconditionalBranch(TerminatorInst *, unsigned);
     inline void eliminateUnconditionalBranch(BranchInst *BI);
     SmallPtrSet<BasicBlock*, 4> CycleDetector;
+    LoopInfo *LI;  // The current loop information
   };
 }
 
@@ -69,6 +72,9 @@ FunctionPass *llvm::createTailDuplicationPass() { return new TailDup(); }
 /// a place it already pointed to earlier; see PR 2323.
 bool TailDup::runOnFunction(Function &F) {
   bool Changed = false;
+
+  LI = &getAnalysis<LoopInfo>();
+
   CycleDetector.clear();
   for (Function::iterator I = F.begin(), E = F.end(); I != E; ) {
     if (shouldEliminateUnconditionalBranch(I->getTerminator(),
@@ -83,6 +89,10 @@ bool TailDup::runOnFunction(Function &F) {
   return Changed;
 }
 
+void TailDup::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.addRequired<LoopInfo>();
+}
+
 /// shouldEliminateUnconditionalBranch - Return true if this branch looks
 /// attractive to eliminate.  We eliminate the branch if the destination basic
 /// block has <= 5 instructions in it, not counting PHI nodes.  In practice,
@@ -186,6 +196,14 @@ bool TailDup::shouldEliminateUnconditionalBranch(TerminatorInst *TI,
   if (!CycleDetector.insert(Dest))
     return false;
 
+  // Avoid non-natural loops:
+  // If a loop header is duplicated, the former natural loop will contain two
+  // paths into the loop --> the loop it not natural anymore. We want to avoid
+  // this, because other optimizaions may fail to improve the loop because of 
+  // this.
+  if (LI->isLoopHeader(Dest))
+    return false;
+
   return true;
 }
 

diff --git a/test/Transforms/TailDup/2008-06-11-AvoidDupLoopHeader.ll b/test/Transforms/TailDup/2008-06-11-AvoidDupLoopHeader.ll
new file mode 100644 (file)
index 0000000..5692ca6
--- /dev/null
+++ b/test/Transforms/TailDup/2008-06-11-AvoidDupLoopHeader.ll
@@ -0,0 +1,27 @@
+; RUN: llvm-as < %s | opt -tailduplicate -taildup-threshold=3 -stats -disable-output |&
+; RUN:   not grep tailduplicate
+
+define i32 @foo(i32 %l) nounwind  {
+entry:
+       %cond = icmp eq i32 %l, 1               ; <i1> [#uses=1]
+       br i1 %cond, label %bb, label %bb9
+
+bb:            ; preds = %entry
+       br label %bb9
+
+bb5:           ; preds = %bb9
+       %tmp7 = call i32 (...)* @bar( i32 %x.0 ) nounwind               ; <i32> [#uses=1]
+       br label %bb9
+
+bb9:           ; preds = %bb5, %bb, %entry
+       %x.0 = phi i32 [ 0, %entry ], [ %tmp7, %bb5 ], [ 1525, %bb ]            ; <i32> [#uses=2]
+       %l_addr.0 = phi i32 [ %l, %entry ], [ %tmp11, %bb5 ], [ %l, %bb ]               ; <i32> [#uses=1]
+       %tmp11 = add i32 %l_addr.0, -1          ; <i32> [#uses=2]
+       %tmp13 = icmp eq i32 %tmp11, -1         ; <i1> [#uses=1]
+       br i1 %tmp13, label %bb15, label %bb5
+
+bb15:          ; preds = %bb9
+       ret i32 %x.0
+}
+
+declare i32 @bar(...)