diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index 59a2852..9236f7c 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -184,22 +184,24 @@
       }
       HInstruction* left = equality_instr->InputAt(0);
       HInstruction* right = equality_instr->InputAt(1);
-      HInstruction* null_instr = nullptr;
+      HInstruction* int_operand = nullptr;
 
-      if ((left->GetType() == Primitive::kPrimNot) && right->IsIntConstant()) {
-        null_instr = right;
-      } else if ((right->GetType() == Primitive::kPrimNot) && left->IsIntConstant()) {
-        null_instr = left;
+      if ((left->GetType() == Primitive::kPrimNot) && (right->GetType() == Primitive::kPrimInt)) {
+        int_operand = right;
+      } else if ((right->GetType() == Primitive::kPrimNot)
+                 && (left->GetType() == Primitive::kPrimInt)) {
+        int_operand = left;
       } else {
         continue;
       }
 
       // If we got here, we are comparing against a reference and the int constant
       // should be replaced with a null constant.
-      if (null_instr->IsIntConstant()) {
-        DCHECK_EQ(0, null_instr->AsIntConstant()->GetValue());
-        equality_instr->ReplaceInput(GetGraph()->GetNullConstant(), null_instr == right ? 1 : 0);
-      }
+      // Both type propagation and redundant phi elimination ensure `int_operand`
+      // can only be the 0 constant.
+      DCHECK(int_operand->IsIntConstant());
+      DCHECK_EQ(0, int_operand->AsIntConstant()->GetValue());
+      equality_instr->ReplaceInput(GetGraph()->GetNullConstant(), int_operand == right ? 1 : 0);
     }
   }
 }
@@ -255,21 +257,18 @@
   PrimitiveTypePropagation type_propagation(GetGraph());
   type_propagation.Run();
 
-  // 5) Fix the type for null constants which are part of an equality comparison.
-  FixNullConstantType();
-
-  // 6) When creating equivalent phis we copy the inputs of the original phi which
-  // may be improperly typed. This will be fixed during the type propagation but
+  // 5) When creating equivalent phis we copy the inputs of the original phi which
+  // may be improperly typed. This was fixed during the type propagation in 4) but
   // as a result we may end up with two equivalent phis with the same type for
   // the same dex register. This pass cleans them up.
   EquivalentPhisCleanup();
 
-  // 7) Mark dead phis again. Step 4) may have introduced new phis.
-  // Step 6) might enable the death of new phis.
+  // 6) Mark dead phis again. Step 4) may have introduced new phis.
+  // Step 5) might enable the death of new phis.
   SsaDeadPhiElimination dead_phis(GetGraph());
   dead_phis.MarkDeadPhis();
 
-  // 8) Now that the graph is correctly typed, we can get rid of redundant phis.
+  // 7) Now that the graph is correctly typed, we can get rid of redundant phis.
   // Note that we cannot do this phase before type propagation, otherwise
   // we could get rid of phi equivalents, whose presence is a requirement for the
   // type propagation phase. Note that this is to satisfy statement (a) of the
@@ -277,6 +276,13 @@
   SsaRedundantPhiElimination redundant_phi(GetGraph());
   redundant_phi.Run();
 
+  // 8) Fix the type for null constants which are part of an equality comparison.
+  // We need to do this after redundant phi elimination, to ensure the only cases
+  // that we can see are reference comparison against 0. The redundant phi
+  // elimination ensures we do not see a phi taking two 0 constants in a HEqual
+  // or HNotEqual.
+  FixNullConstantType();
+
   // 9) Make sure environments use the right phi "equivalent": a phi marked dead
   // can have a phi equivalent that is not dead. We must therefore update
   // all environment uses of the dead phi to use its equivalent. Note that there
diff --git a/test/498-type-propagation/expected.txt b/test/498-type-propagation/expected.txt
new file mode 100644
index 0000000..ccaf6f8
--- /dev/null
+++ b/test/498-type-propagation/expected.txt
@@ -0,0 +1 @@
+Enter
diff --git a/test/498-type-propagation/info.txt b/test/498-type-propagation/info.txt
new file mode 100644
index 0000000..b895e91
--- /dev/null
+++ b/test/498-type-propagation/info.txt
@@ -0,0 +1,2 @@
+Regression test for the SSA building of the optimizing
+compiler. See comment in smali file.
diff --git a/test/498-type-propagation/smali/TypePropagation.smali b/test/498-type-propagation/smali/TypePropagation.smali
new file mode 100644
index 0000000..088ca89
--- /dev/null
+++ b/test/498-type-propagation/smali/TypePropagation.smali
@@ -0,0 +1,30 @@
+# Copyright (C) 2015 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#      http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+.class public LTypePropagation;
+
+.super Ljava/lang/Object;
+
+.method public static method([I)V
+   .registers 2
+   const/4 v0, 0
+   # When building the SSA graph, we will create a phi for v0, which will be of type
+   # integer. Only when we get rid of that phi in the redundant phi elimination will
+   # we realize it's just null.
+   :start
+   if-eq v1, v0, :end
+     if-eq v1, v0, :start
+   :end
+   return-void
+.end method
diff --git a/test/498-type-propagation/src/Main.java b/test/498-type-propagation/src/Main.java
new file mode 100644
index 0000000..7a14172
--- /dev/null
+++ b/test/498-type-propagation/src/Main.java
@@ -0,0 +1,29 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+import java.lang.reflect.Method;
+
+public class Main {
+  public static void main(String[] args) throws Exception {
+    // Workaround for b/18051191.
+    System.out.println("Enter");
+    Class<?> c = Class.forName("TypePropagation");
+    Method m = c.getMethod("method", int[].class);
+    int[] array = new int[7];
+    Object[] arguments = { array };
+    m.invoke(null, arguments);
+  }
+}