From f143b79b78d1d244809fa59320f2af2edf4e1a86 Mon Sep 17 00:00:00 2001
From: Andrew Trick <atrick@apple.com>
Date: Tue, 4 Oct 2011 03:50:44 +0000
Subject: [PATCH] LSR should avoid redundant edge splitting.

This handles the case in which LSR rewrites an IV user that is a phi and
splits critical edges originating from a switch.
Fixes <rdar://problem/6453893> LSR is not splitting edges "nicely"


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141059 91177308-0d34-0410-b5e6-96231b3b80d8
---
 .../llvm/Transforms/Utils/BasicBlockUtils.h   |  9 ++--
 lib/Transforms/Scalar/LoopStrengthReduce.cpp  |  4 +-
 lib/Transforms/Utils/BreakCriticalEdges.cpp   |  5 ++-
 .../2011-10-03-CritEdgeMerge.ll               | 43 +++++++++++++++++++
 4 files changed, 55 insertions(+), 6 deletions(-)
 create mode 100644 test/Transforms/LoopStrengthReduce/2011-10-03-CritEdgeMerge.ll

diff --git a/include/llvm/Transforms/Utils/BasicBlockUtils.h b/include/llvm/Transforms/Utils/BasicBlockUtils.h
index 97364512ebf..6fcd160e64e 100644
--- a/include/llvm/Transforms/Utils/BasicBlockUtils.h
+++ b/include/llvm/Transforms/Utils/BasicBlockUtils.h
@@ -109,7 +109,8 @@ bool isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum,
 /// to.
 ///
 BasicBlock *SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum,
-                              Pass *P = 0, bool MergeIdenticalEdges = false);
+                              Pass *P = 0, bool MergeIdenticalEdges = false,
+                              bool DontDeleteUselessPHIs = false);
 
 inline BasicBlock *SplitCriticalEdge(BasicBlock *BB, succ_iterator SI,
                                      Pass *P = 0) {
@@ -136,13 +137,15 @@ inline bool SplitCriticalEdge(BasicBlock *Succ, pred_iterator PI, Pass *P = 0) {
 /// described above.
 inline BasicBlock *SplitCriticalEdge(BasicBlock *Src, BasicBlock *Dst,
                                      Pass *P = 0,
-                                     bool MergeIdenticalEdges = false) {
+                                     bool MergeIdenticalEdges = false,
+                                     bool DontDeleteUselessPHIs = false) {
   TerminatorInst *TI = Src->getTerminator();
   unsigned i = 0;
   while (1) {
     assert(i != TI->getNumSuccessors() && "Edge doesn't exist!");
     if (TI->getSuccessor(i) == Dst)
-      return SplitCriticalEdge(TI, i, P, MergeIdenticalEdges);
+      return SplitCriticalEdge(TI, i, P, MergeIdenticalEdges,
+                               DontDeleteUselessPHIs);
     ++i;
   }
 }
diff --git a/lib/Transforms/Scalar/LoopStrengthReduce.cpp b/lib/Transforms/Scalar/LoopStrengthReduce.cpp
index 7b1a340156d..4b6c55e1627 100644
--- a/lib/Transforms/Scalar/LoopStrengthReduce.cpp
+++ b/lib/Transforms/Scalar/LoopStrengthReduce.cpp
@@ -3677,7 +3677,9 @@ void LSRInstance::RewriteForPHI(PHINode *PN,
           // Split the critical edge.
           BasicBlock *NewBB = 0;
           if (!Parent->isLandingPad()) {
-            NewBB = SplitCriticalEdge(BB, Parent, P);
+            NewBB = SplitCriticalEdge(BB, Parent, P,
+                                      /*MergeIdenticalEdges=*/true,
+                                      /*DontDeleteUselessPhis=*/true);
           } else {
             SmallVector<BasicBlock*, 2> NewBBs;
             SplitLandingPadPredecessors(Parent, BB, "", "", P, NewBBs);
diff --git a/lib/Transforms/Utils/BreakCriticalEdges.cpp b/lib/Transforms/Utils/BreakCriticalEdges.cpp
index 4648f496450..c0529108815 100644
--- a/lib/Transforms/Utils/BreakCriticalEdges.cpp
+++ b/lib/Transforms/Utils/BreakCriticalEdges.cpp
@@ -167,7 +167,8 @@ static void CreatePHIsForSplitLoopExit(SmallVectorImpl<BasicBlock *> &Preds,
 /// to.
 ///
 BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum,
-                                    Pass *P, bool MergeIdenticalEdges) {
+                                    Pass *P, bool MergeIdenticalEdges,
+                                    bool DontDeleteUselessPhis) {
   if (!isCriticalEdge(TI, SuccNum, MergeIdenticalEdges)) return 0;
 
   assert(!isa<IndirectBrInst>(TI) &&
@@ -224,7 +225,7 @@ BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum,
       if (TI->getSuccessor(i) != DestBB) continue;
 
       // Remove an entry for TIBB from DestBB phi nodes.
-      DestBB->removePredecessor(TIBB);
+      DestBB->removePredecessor(TIBB, DontDeleteUselessPhis);
 
       // We found another edge to DestBB, go to NewBB instead.
       TI->setSuccessor(i, NewBB);
diff --git a/test/Transforms/LoopStrengthReduce/2011-10-03-CritEdgeMerge.ll b/test/Transforms/LoopStrengthReduce/2011-10-03-CritEdgeMerge.ll
new file mode 100644
index 00000000000..a6996a81fb0
--- /dev/null
+++ b/test/Transforms/LoopStrengthReduce/2011-10-03-CritEdgeMerge.ll
@@ -0,0 +1,43 @@
+; RUN: opt -loop-reduce -S < %s | FileCheck %s
+;
+; Test LSR's use of SplitCriticalEdge during phi rewriting.
+; Verify that identical edges are merged. rdar://problem/6453893
+
+target triple = "x86-apple-darwin"
+
+; CHECK: @test
+; CHECK: bb89:
+; CHECK: phi i8* [ %lsr.iv.next1, %bbA.bb89_crit_edge ], [ %lsr.iv.next1, %bbB.bb89_crit_edge ]{{$}}
+
+define i8* @test() {
+entry:
+  br label %loop
+
+loop:
+  %rec = phi i32 [ %next, %loop ], [ 0, %entry ]
+  %next = add i32 %rec, 1
+  %tmp75 = getelementptr i8* null, i32 %next
+  br i1 false, label %loop, label %loopexit
+
+loopexit:
+  br i1 false, label %bbA, label %bbB
+
+bbA:
+  switch i32 0, label %bb89 [
+    i32 47, label %bb89
+    i32 58, label %bb89
+  ]
+
+bbB:
+  switch i8 0, label %bb89 [
+    i8 47, label %bb89
+    i8 58, label %bb89
+  ]
+
+bb89:
+  %tmp75phi = phi i8* [ %tmp75, %bbA ], [ %tmp75, %bbA ], [ %tmp75, %bbA ], [ %tmp75, %bbB ], [ %tmp75, %bbB ], [ %tmp75, %bbB ]
+  br label %exit
+
+exit:
+  ret i8* %tmp75phi
+}
-- 
2.34.1