Index: llvm/trunk/lib/CodeGen/CodeGenPrepare.cpp
===================================================================
--- llvm/trunk/lib/CodeGen/CodeGenPrepare.cpp
+++ llvm/trunk/lib/CodeGen/CodeGenPrepare.cpp
@@ -3332,7 +3332,7 @@
         // So the values are different and does not match. So we need them to
         // match. (But we register no more than one match per PHI node, so that
         // we won't later try to replace them twice.)
-        if (!MatchedPHIs.insert(FirstPhi).second)
+        if (MatchedPHIs.insert(FirstPhi).second)
           Matcher.insert({ FirstPhi, SecondPhi });
         // But me must check it.
         WorkList.push_back({ FirstPhi, SecondPhi });
Index: llvm/trunk/test/CodeGen/X86/codegen-prepare-replacephi2.mir
===================================================================
--- llvm/trunk/test/CodeGen/X86/codegen-prepare-replacephi2.mir
+++ llvm/trunk/test/CodeGen/X86/codegen-prepare-replacephi2.mir
@@ -0,0 +1,68 @@
+# RUN: llc -run-pass=codegenprepare -o - %s | FileCheck %s
+
+# REQUIRES: default_triple
+
+# This testcase without the accompanying fix triggers the assert
+# "Replacement PHI node is already replaced."
+
+--- |
+
+  define void @f1() {
+  entry:
+    %arrayidx = getelementptr inbounds [2 x i16], [2 x i16]* undef, i16 0, i16 2
+    %0 = bitcast i16* %arrayidx to i32*
+    %1 = bitcast [2 x i16]* undef to i32*
+    br label %for.cond
+
+  for.cond.loopexit:
+    br label %for.cond
+
+  for.cond:
+    %2 = phi i32* [ %0, %entry ], [ %12, %for.cond.loopexit ]
+    %3 = phi i32* [ %0, %entry ], [ %14, %for.cond.loopexit ]
+    br label %for.body
+
+  for.body:
+    %4 = phi i32* [ %3, %for.cond ], [ %14, %cleanup ]
+    %5 = phi i32* [ %2, %for.cond ], [ %13, %cleanup ]
+    %6 = phi i32* [ %2, %for.cond ], [ %12, %cleanup ]
+    br i1 undef, label %for.cond2.preheader, label %if.then
+
+  for.cond2.preheader:
+    br label %for.cond2
+
+  if.then:
+    store i32 undef, i32* %4, align 1
+    br label %cleanup
+
+  for.cond2:
+    %7 = phi i32* [ %10, %for.inc ], [ %6, %for.cond2.preheader ]
+    %8 = phi i32* [ %11, %for.inc ], [ %5, %for.cond2.preheader ]
+    %9 = phi i32* [ %11, %for.inc ], [ %4, %for.cond2.preheader ]
+    br i1 undef, label %for.inc, label %if.then5
+
+  if.then5:
+    br i1 icmp ne (i16 2, i16 0), label %cleanup.loopexit, label %if.end
+
+  if.end:
+    br label %for.inc
+
+  for.inc:
+    %10 = phi i32* [ %7, %if.end ], [ %1, %for.cond2 ]
+    %11 = phi i32* [ %8, %if.end ], [ %1, %for.cond2 ]
+    br label %for.cond2
+
+  cleanup.loopexit:
+    br label %cleanup
+
+  cleanup:
+    %12 = phi i32* [ %6, %if.then ], [ %7, %cleanup.loopexit ]
+    %13 = phi i32* [ %5, %if.then ], [ %8, %cleanup.loopexit ]
+    %14 = phi i32* [ %4, %if.then ], [ %9, %cleanup.loopexit ]
+    br i1 true, label %for.cond.loopexit, label %for.body
+  }
+
+...
+
+# Sanity check to verify that something got through.
+# CHECK-LABEL: entry: