Index: lib/Transforms/Scalar/SROA.cpp
===================================================================
--- lib/Transforms/Scalar/SROA.cpp
+++ lib/Transforms/Scalar/SROA.cpp
@@ -3094,6 +3094,59 @@
   return SubTy;
 }
 
+/// \brief Return true if the value of PN originates from a value
+/// other than Source.
+///
+/// This function performs a standard depth-first search along the use-def
+/// chains of the PHI nodes. If the searching reaches a non-PHI other than
+/// Source, it stops and returns true.
+static bool
+PHINodeOriginatesFromOther(PHINode *PN, SmallPtrSetImpl<PHINode *> &Visited,
+                           SmallPtrSetImpl<PHINode *> &OriginatesFromOther,
+                           Value *Source) {
+  if (Visited.count(PN))
+    return OriginatesFromOther.count(PN);
+  Visited.insert(PN);
+  for (unsigned I = 0; I < PN->getNumIncomingValues(); ++I) {
+    Value *IV = PN->getIncomingValue(I);
+    if (PHINode *IncomingPN = dyn_cast<PHINode>(IV)) {
+      if (PHINodeOriginatesFromOther(IncomingPN, Visited, OriginatesFromOther,
+                                     Source)) {
+        OriginatesFromOther.insert(PN);
+        return true;
+      }
+    } else {
+      if (IV != Source) {
+        OriginatesFromOther.insert(PN);
+        return true;
+      }
+    }
+  }
+  return false;
+}
+
+/// \brief Simplify the PHI nodes in PHIUsers that are equivalent to NewAI.
+///
+/// Remove from PHIUsers PHI nodes that are equivalent to NewAI, and replace
+/// these PHI nodes with NewAI.
+static void
+simplifyPHINodesEquivalentToNewAlloca(SmallPtrSetImpl<PHINode *> &PHIUsers,
+                                      AllocaInst *NewAI) {
+  // Visited serves to break cycles during DFS.  OriginatesFromOther serves as a
+  // cache: if we already know that a PHI node originates from other values, we
+  // needn't search from it again.
+  SmallPtrSet<PHINode *, 8> Visited, OriginatesFromOther, ToDelete;
+  for (auto PN : PHIUsers) {
+    if (!PHINodeOriginatesFromOther(PN, Visited, OriginatesFromOther, NewAI))
+      ToDelete.insert(PN);
+  }
+  for (auto PN: ToDelete) {
+    PHIUsers.erase(PN);
+    PN->replaceAllUsesWith(NewAI);
+    PN->eraseFromParent();
+  }
+}
+
 /// \brief Rewrite an alloca partition's users.
 ///
 /// This routine drives both of the rewriting goals of the SROA pass. It tries
@@ -3201,6 +3254,10 @@
   MaxUsesPerAllocaPartition =
       std::max<unsigned>(NumUses, MaxUsesPerAllocaPartition);
 
+  // Simplify PHI nodes in PHIUsers that are trivially equivalent to NewAI, so
+  // that we can promote them to registers more effectively.
+  simplifyPHINodesEquivalentToNewAlloca(PHIUsers, NewAI);
+
   // Now that we've processed all the slices in the new partition, check if any
   // PHIs or Selects would block promotion.
   for (SmallPtrSetImpl<PHINode *>::iterator I = PHIUsers.begin(),
Index: test/Transforms/SROA/phi-and-select.ll
===================================================================
--- test/Transforms/SROA/phi-and-select.ll
+++ test/Transforms/SROA/phi-and-select.ll
@@ -501,3 +501,68 @@
 ; CHECK-NOT: load
 ; CHECK: ret float %[[phi]]
 }
+
+; Verifies we fixed PR20425. We should be able to promote all alloca's to
+; registers in this test.
+;
+; %0 = slice
+; %1 = slice
+; %2 = phi(%0, %1) // == slice
+define float @simplify_phi_nodes_that_equal_slice(i1 %cond, float* %temp) {
+entry:
+  %arr = alloca [4 x float], align 4
+  br i1 %cond, label %then, label %else
+
+then:
+  %0 = getelementptr inbounds [4 x float]* %arr, i64 0, i64 3
+  store float 1.000000e+00, float* %0, align 4
+  br label %merge
+
+else:
+  %1 = getelementptr inbounds [4 x float]* %arr, i64 0, i64 3
+  store float 2.000000e+00, float* %1, align 4
+  br label %merge
+
+merge:
+  %2 = phi float* [ %0, %then ], [ %1, %else ]
+  store float 0.000000e+00, float* %temp, align 4
+  %3 = load float* %2, align 4
+  ret float %3
+}
+; CHECK-LABEL: @simplify_phi_nodes_that_equal_slice(
+; CHECK-NOT: alloca
+
+; A slightly complicated example for PR20425.
+;
+; %0 = slice
+; %1 = phi(%0) // == slice
+; %2 = slice
+; %3 = phi(%1, %2) // == slice
+define float @simplify_phi_nodes_that_equal_slice_2(i1 %cond, float* %temp) {
+entry:
+  %arr = alloca [4 x float], align 4
+  br i1 %cond, label %then, label %else
+
+then:
+  %0 = getelementptr inbounds [4 x float]* %arr, i64 0, i64 3
+  store float 1.000000e+00, float* %0, align 4
+  br label %then2
+
+then2:
+  %1 = phi float* [ %0, %then ]
+  store float 2.000000e+00, float* %1, align 4
+  br label %merge
+
+else:
+  %2 = getelementptr inbounds [4 x float]* %arr, i64 0, i64 3
+  store float 3.000000e+00, float* %2, align 4
+  br label %merge
+
+merge:
+  %3 = phi float* [ %1, %then2 ], [ %2, %else ]
+  store float 0.000000e+00, float* %temp, align 4
+  %4 = load float* %3, align 4
+  ret float %4
+}
+; CHECK-LABEL: @simplify_phi_nodes_that_equal_slice_2(
+; CHECK-NOT: alloca