PHI elimination should not break back edge. It can cause some significant code placement issues. rdar://8263994

good:
LBB0_2:
  mov     r2, r0
  . . .
  mov     r1, r2
  bne     LBB0_2

bad:
LBB0_2:
  mov     r2, r0
  . . .
@ BB#3:
  mov     r1, r2
  b       LBB0_2


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

4 files changed, 45 insertions, 7 deletions

diff --git a/lib/CodeGen/MachineBasicBlock.cpp b/lib/CodeGen/MachineBasicBlock.cpp
index a27ee47943..895653d18d 100644
--- a/lib/CodeGen/MachineBasicBlock.cpp
+++ b/lib/CodeGen/MachineBasicBlock.cpp
@@ -439,6 +439,14 @@ MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P) {
   if (TII->AnalyzeBranch(*this, TBB, FBB, Cond))
     return NULL;
 
+  // Avoid splitting backedges of loops. It would introduce small out-of-line
+  // blocks into the loop which is very bad for code placement.
+  if (this == Succ)
+    return NULL;
+  MachineLoopInfo *MLI = P->getAnalysisIfAvailable<MachineLoopInfo>();
+  if (MLI->isLoopHeader(Succ))
+    return NULL;
+
   MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock();
   MF->insert(llvm::next(MachineFunction::iterator(this)), NMBB);
   DEBUG(dbgs() << "PHIElimination splitting critical edge:"
@@ -471,8 +479,7 @@ MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P) {
         P->getAnalysisIfAvailable<MachineDominatorTree>())
     MDT->addNewBlock(NMBB, this);
 
-  if (MachineLoopInfo *MLI =
-        P->getAnalysisIfAvailable<MachineLoopInfo>())
+  if (MLI)
     if (MachineLoop *TIL = MLI->getLoopFor(this)) {
       // If one or the other blocks were not in a loop, the new block is not
       // either, and thus LI doesn't need to be updated.
diff --git a/lib/CodeGen/PHIElimination.cpp b/lib/CodeGen/PHIElimination.cpp
index 7bf0aa23af..105f20b448 100644
--- a/lib/CodeGen/PHIElimination.cpp
+++ b/lib/CodeGen/PHIElimination.cpp
@@ -20,6 +20,7 @@
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Function.h"
@@ -44,9 +45,9 @@ char &llvm::PHIEliminationID = PHIElimination::ID;
 
 void llvm::PHIElimination::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addPreserved<LiveVariables>();
+  AU.addRequired<MachineLoopInfo>();
   AU.addPreserved<MachineDominatorTree>();
-  // rdar://7401784 This would be nice:
-  // AU.addPreservedID(MachineLoopInfoID);
+  AU.addPreservedID(MachineLoopInfoID);
   MachineFunctionPass::getAnalysisUsage(AU);
 }
 
@@ -382,6 +383,7 @@ bool llvm::PHIElimination::SplitPHIEdges(MachineFunction &MF,
   if (MBB.empty() || !MBB.front().isPHI() || MBB.isLandingPad())
     return false;   // Quick exit for basic blocks without PHIs.
 
+  bool Changed = false;
   for (MachineBasicBlock::const_iterator BBI = MBB.begin(), BBE = MBB.end();
        BBI != BBE && BBI->isPHI(); ++BBI) {
     for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
@@ -391,7 +393,7 @@ bool llvm::PHIElimination::SplitPHIEdges(MachineFunction &MF,
       // (not considering PHI nodes). If the register is live in to this block
       // anyway, we would gain nothing from splitting.
       if (!LV.isLiveIn(Reg, MBB) && LV.isLiveOut(Reg, *PreMBB))
-        PreMBB->SplitCriticalEdge(&MBB, this);
+        Changed |= PreMBB->SplitCriticalEdge(&MBB, this) != 0;
     }
   }
   return true;
diff --git a/test/CodeGen/ARM/code-placement.ll b/test/CodeGen/ARM/code-placement.ll
new file mode 100644
index 0000000000..25c556889f
--- /dev/null
+++ b/test/CodeGen/ARM/code-placement.ll
@@ -0,0 +1,29 @@
+; RUN: llc < %s -mtriple=armv7-apple-darwin | FileCheck %s
+; PHI elimination shouldn't break backedge.
+; rdar://8263994
+
+%struct.list_data_s = type { i16, i16 }
+%struct.list_head = type { %struct.list_head*, %struct.list_data_s* }
+
+define arm_apcscc %struct.list_head* @t(%struct.list_head* %list) nounwind {
+entry:
+  %0 = icmp eq %struct.list_head* %list, null
+  br i1 %0, label %bb2, label %bb
+
+bb:
+; CHECK: LBB0_2:
+; CHECK: bne LBB0_2
+; CHECK-NOT: b LBB0_2
+; CHECK: bx lr
+  %list_addr.05 = phi %struct.list_head* [ %2, %bb ], [ %list, %entry ]
+  %next.04 = phi %struct.list_head* [ %list_addr.05, %bb ], [ null, %entry ]
+  %1 = getelementptr inbounds %struct.list_head* %list_addr.05, i32 0, i32 0
+  %2 = load %struct.list_head** %1, align 4
+  store %struct.list_head* %next.04, %struct.list_head** %1, align 4
+  %3 = icmp eq %struct.list_head* %2, null
+  br i1 %3, label %bb2, label %bb
+
+bb2:
+  %next.0.lcssa = phi %struct.list_head* [ null, %entry ], [ %list_addr.05, %bb ]
+  ret %struct.list_head* %next.0.lcssa
+}
diff --git a/test/CodeGen/X86/lsr-reuse.ll b/test/CodeGen/X86/lsr-reuse.ll
index b7e69b84bf..d2ff58be10 100644
--- a/test/CodeGen/X86/lsr-reuse.ll
+++ b/test/CodeGen/X86/lsr-reuse.ll
@@ -464,7 +464,7 @@ bb5:                                              ; preds = %bb3, %entry
 
 ; And the one at %bb68, where we want to be sure to use superhero mode:
 
-; CHECK:      BB10_10:
+; CHECK:      BB10_9:
 ; CHECK-NEXT:   movaps  48(%r{{[^,]*}}), %xmm{{.*}}
 ; CHECK-NEXT:   mulps   %xmm{{.*}}, %xmm{{.*}}
 ; CHECK-NEXT:   movaps  32(%r{{[^,]*}}), %xmm{{.*}}
@@ -484,7 +484,7 @@ bb5:                                              ; preds = %bb3, %entry
 ; CHECK-NEXT:   addq    $64, %r{{.*}}
 ; CHECK-NEXT:   addq    $64, %r{{.*}}
 ; CHECK-NEXT:   addq    $-16, %r{{.*}}
-; CHECK-NEXT: BB10_11:
+; CHECK-NEXT: BB10_10:
 ; CHECK-NEXT:   cmpq    $15, %r{{.*}}
 ; CHECK-NEXT:   jg