Index: lib/Transforms/Scalar/SROA.cpp
===================================================================
--- lib/Transforms/Scalar/SROA.cpp
+++ lib/Transforms/Scalar/SROA.cpp
@@ -3094,6 +3094,71 @@
   return SubTy;
 }
 
+/// \brief Return true if PN is equivalent to NewAlloca.
+///
+/// This function performs a standard depth-first search along the incoming
+/// values of PN. If the searching reaches a non-PHI other than
+/// NewAlloca, it stops and returns false. This computation is conservative:
+/// it may return false when PN is equivalent to NewAlloca, but won't return
+/// return true when PN is not equivalent to NewAlloca.
+///
+/// \param PN The PHI node.
+/// \param EquivalentToNewalloca A map that caches the results of this function
+///                              to avoid redundant computation.
+/// \param NewAlloca The value we want to prove PN equivalent to.
+static bool
+PHINodeEquivalentToNewAlloca(PHINode *PN,
+                             DenseMap<PHINode *, bool> &EquivalentToNewAlloca,
+                             Value *NewAlloca) {
+  // If we already ran this function on PN, return the cached result.
+  if (EquivalentToNewAlloca.count(PN))
+    return EquivalentToNewAlloca.find(PN)->second;
+
+  // Create a slot in EquivalentToNewAlloca to break potential cycles formed by
+  // incoming ediges of PHI nodes.
+  bool &Equivalent = EquivalentToNewAlloca[PN];
+  // Initialize the result as true, and reset it when found it reaches
+  // non-PHI other than NewAlloca.
+  Equivalent = true;
+  for (unsigned I = 0; I < PN->getNumIncomingValues(); ++I) {
+    Value *IV = PN->getIncomingValue(I);
+    if (PHINode *IncomingPN = dyn_cast<PHINode>(IV)) {
+      if (!PHINodeEquivalentToNewAlloca(IncomingPN, EquivalentToNewAlloca,
+                                       NewAlloca)) {
+        Equivalent = false;
+        return false;
+      }
+    } else {
+      if (IV != NewAlloca) {
+        Equivalent = false;
+        return false;
+      }
+    }
+  }
+  return true;
+}
+
+/// \brief Simplify the PHI nodes in PHIUsers that are equivalent to NewAlloca.
+///
+/// Remove from PHIUsers PHI nodes that are equivalent to NewAlloca, and replace
+/// these PHI nodes with NewAlloca.
+static void
+simplifyPHINodesEquivalentToNewAlloca(SmallPtrSetImpl<PHINode *> &PHIUsers,
+                                      AllocaInst *NewAlloca) {
+  // EquivalentToNewAlloca caches the result of PHINodeEquivalentToNewAlloca.
+  DenseMap<PHINode *, bool> EquivalentToNewAlloca;
+  for (auto PN : PHIUsers)
+    PHINodeEquivalentToNewAlloca(PN, EquivalentToNewAlloca, NewAlloca);
+  for (auto MapEntry : EquivalentToNewAlloca) {
+    if (MapEntry.second) {
+      PHINode *PN = MapEntry.first;
+      PHIUsers.erase(PN);
+      PN->replaceAllUsesWith(NewAlloca);
+      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 +3266,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