diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc
index 69f031a..83d04b1 100644
--- a/compiler/optimizing/code_generator_x86_64.cc
+++ b/compiler/optimizing/code_generator_x86_64.cc
@@ -2896,7 +2896,7 @@
       __ movss(Address(CpuRegister(RSP), destination.GetStackIndex()),
                source.As<XmmRegister>());
     } else {
-      DCHECK(destination.IsDoubleStackSlot());
+      DCHECK(destination.IsDoubleStackSlot()) << destination;
       __ movsd(Address(CpuRegister(RSP), destination.GetStackIndex()),
                source.As<XmmRegister>());
     }
diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index 1953241..5d712fe 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -342,4 +342,72 @@
   }
 }
 
+static Primitive::Type PrimitiveKind(Primitive::Type type) {
+  switch (type) {
+    case Primitive::kPrimBoolean:
+    case Primitive::kPrimByte:
+    case Primitive::kPrimShort:
+    case Primitive::kPrimChar:
+    case Primitive::kPrimInt:
+      return Primitive::kPrimInt;
+    default:
+      return type;
+  }
+}
+
+void SSAChecker::VisitCondition(HCondition* op) {
+  VisitInstruction(op);
+  // TODO: check inputs types, and special case the `null` check.
+  if (op->GetType() != Primitive::kPrimBoolean) {
+    std::stringstream error;
+    error << "Condition " << op->DebugName() << " " << op->GetId()
+          << " has a non-boolean result type: "
+          << op->GetType() << ".";
+    errors_.push_back(error.str());
+  }
+}
+
+void SSAChecker::VisitBinaryOperation(HBinaryOperation* op) {
+  VisitInstruction(op);
+  if (op->IsUShr() || op->IsShr() || op->IsShl()) {
+    if (PrimitiveKind(op->InputAt(1)->GetType()) != Primitive::kPrimInt) {
+      std::stringstream error;
+      error << "Shift operation " << op->DebugName() << " " << op->GetId()
+            << " has a non-int kind second input: "
+            << op->InputAt(1)->DebugName() << " of type " << op->InputAt(1)->GetType()
+            << ".";
+      errors_.push_back(error.str());
+    }
+  } else {
+    if (PrimitiveKind(op->InputAt(1)->GetType()) != PrimitiveKind(op->InputAt(0)->GetType())) {
+      std::stringstream error;
+      error << "Binary operation " << op->DebugName() << " " << op->GetId()
+            << " has inputs of different type: "
+            << op->InputAt(0)->GetType() << ", and " << op->InputAt(1)->GetType()
+            << ".";
+      errors_.push_back(error.str());
+    }
+  }
+
+  if (op->IsCompare()) {
+    if (op->GetType() != Primitive::kPrimInt) {
+      std::stringstream error;
+      error << "Compare operation " << op->GetId()
+            << " has a non-int result type: "
+            << op->GetType() << ".";
+      errors_.push_back(error.str());
+    }
+  } else {
+    // Use the first input, so that we can also make this check for shift operations.
+    if (PrimitiveKind(op->GetType()) != PrimitiveKind(op->InputAt(0)->GetType())) {
+      std::stringstream error;
+      error << "Binary operation " << op->DebugName() << " " << op->GetId()
+            << " has a result type different than its input type: "
+            << op->GetType() << ", and " << op->InputAt(1)->GetType()
+            << ".";
+      errors_.push_back(error.str());
+    }
+  }
+}
+
 }  // namespace art
diff --git a/compiler/optimizing/graph_checker.h b/compiler/optimizing/graph_checker.h
index 8ba8cb1..b6c9f17 100644
--- a/compiler/optimizing/graph_checker.h
+++ b/compiler/optimizing/graph_checker.h
@@ -24,11 +24,11 @@
 namespace art {
 
 // A control-flow graph visitor performing various checks.
-class GraphChecker : public HGraphVisitor {
+class GraphChecker : public HGraphDelegateVisitor {
  public:
   GraphChecker(ArenaAllocator* allocator, HGraph* graph,
                const char* dump_prefix = "art::GraphChecker: ")
-    : HGraphVisitor(graph),
+    : HGraphDelegateVisitor(graph),
       allocator_(allocator),
       dump_prefix_(dump_prefix) {}
 
@@ -36,10 +36,10 @@
   virtual void Run() { VisitInsertionOrder(); }
 
   // Check `block`.
-  virtual void VisitBasicBlock(HBasicBlock* block) OVERRIDE;
+  void VisitBasicBlock(HBasicBlock* block) OVERRIDE;
 
   // Check `instruction`.
-  virtual void VisitInstruction(HInstruction* instruction) OVERRIDE;
+  void VisitInstruction(HInstruction* instruction) OVERRIDE;
 
   // Was the last visit of the graph valid?
   bool IsValid() const {
@@ -82,7 +82,7 @@
     : GraphChecker(allocator, graph, "art::SSAChecker: ") {}
 
   // Check the whole graph (in reverse post-order).
-  virtual void Run() {
+  void Run() OVERRIDE {
     // VisitReversePostOrder is used instead of VisitInsertionOrder,
     // as the latter might visit dead blocks removed by the dominator
     // computation.
@@ -90,13 +90,15 @@
   }
 
   // Perform SSA form checks on `block`.
-  virtual void VisitBasicBlock(HBasicBlock* block) OVERRIDE;
+  void VisitBasicBlock(HBasicBlock* block) OVERRIDE;
   // Loop-related checks from block `loop_header`.
   void CheckLoop(HBasicBlock* loop_header);
 
   // Perform SSA form checks on instructions.
-  virtual void VisitInstruction(HInstruction* instruction) OVERRIDE;
-  virtual void VisitPhi(HPhi* phi) OVERRIDE;
+  void VisitInstruction(HInstruction* instruction) OVERRIDE;
+  void VisitPhi(HPhi* phi) OVERRIDE;
+  void VisitBinaryOperation(HBinaryOperation* op) OVERRIDE;
+  void VisitCondition(HCondition* op) OVERRIDE;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(SSAChecker);
diff --git a/compiler/optimizing/gvn.h b/compiler/optimizing/gvn.h
index a841d5f..8e739cb 100644
--- a/compiler/optimizing/gvn.h
+++ b/compiler/optimizing/gvn.h
@@ -166,10 +166,10 @@
 /**
  * Optimization phase that removes redundant instruction.
  */
-class GlobalValueNumberer : public HOptimization {
+class GlobalValueNumberer : public ValueObject {
  public:
   GlobalValueNumberer(ArenaAllocator* allocator, HGraph* graph)
-      : HOptimization(graph, true, "GVN"),
+      : graph_(graph),
         allocator_(allocator),
         block_effects_(allocator, graph->GetBlocks().Size()),
         loop_effects_(allocator, graph->GetBlocks().Size()),
@@ -187,7 +187,7 @@
     }
   }
 
-  void Run() OVERRIDE;
+  void Run();
 
  private:
   // Per-block GVN. Will also update the ValueSet of the dominated and
@@ -202,6 +202,8 @@
   SideEffects GetLoopEffects(HBasicBlock* block) const;
   SideEffects GetBlockEffects(HBasicBlock* block) const;
 
+  HGraph* graph_;
+
   ArenaAllocator* const allocator_;
 
   // Side effects of individual blocks, that is the union of the side effects
@@ -224,6 +226,19 @@
   DISALLOW_COPY_AND_ASSIGN(GlobalValueNumberer);
 };
 
+class GVNOptimization : public HOptimization {
+ public:
+  explicit GVNOptimization(HGraph* graph) : HOptimization(graph, true, "GVN") {}
+
+  void Run() OVERRIDE {
+    GlobalValueNumberer gvn(graph_->GetArena(), graph_);
+    gvn.Run();
+  }
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(GVNOptimization);
+};
+
 }  // namespace art
 
 #endif  // ART_COMPILER_OPTIMIZING_GVN_H_
diff --git a/compiler/optimizing/optimization.cc b/compiler/optimizing/optimization.cc
index d1178d5..b99f678 100644
--- a/compiler/optimizing/optimization.cc
+++ b/compiler/optimizing/optimization.cc
@@ -27,13 +27,15 @@
       SSAChecker checker(graph_->GetArena(), graph_);
       checker.Run();
       if (!checker.IsValid()) {
-        LOG(FATAL) << Dumpable<SSAChecker>(checker);
+        LOG(FATAL) << "Error after " << GetPassName() << ": "
+                   << Dumpable<SSAChecker>(checker);
       }
     } else {
       GraphChecker checker(graph_->GetArena(), graph_);
       checker.Run();
       if (!checker.IsValid()) {
-        LOG(FATAL) << Dumpable<GraphChecker>(checker);
+        LOG(FATAL) << "Error after " << GetPassName() << ": "
+                   << Dumpable<GraphChecker>(checker);
       }
     }
   }
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 42ac77d..d8533eb 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -35,6 +35,7 @@
 #include "nodes.h"
 #include "prepare_for_register_allocation.h"
 #include "register_allocator.h"
+#include "ssa_builder.h"
 #include "ssa_phi_elimination.h"
 #include "ssa_liveness_analysis.h"
 #include "utils/arena_allocator.h"
@@ -191,21 +192,31 @@
 }
 
 static void RunOptimizations(HGraph* graph, const HGraphVisualizer& visualizer) {
+  TransformToSsa ssa(graph);
   HDeadCodeElimination opt1(graph);
   HConstantFolding opt2(graph);
   SsaRedundantPhiElimination opt3(graph);
   SsaDeadPhiElimination opt4(graph);
   InstructionSimplifier opt5(graph);
-  GlobalValueNumberer opt6(graph->GetArena(), graph);
+  GVNOptimization opt6(graph);
   InstructionSimplifier opt7(graph);
 
-  HOptimization* optimizations[] = { &opt1, &opt2, &opt3, &opt4, &opt5, &opt6, &opt7 };
+  HOptimization* optimizations[] = {
+    &ssa,
+    &opt1,
+    &opt2,
+    &opt3,
+    &opt4,
+    &opt5,
+    &opt6,
+    &opt7
+  };
 
   for (size_t i = 0; i < arraysize(optimizations); ++i) {
     HOptimization* optimization = optimizations[i];
     optimization->Run();
-    optimization->Check();
     visualizer.DumpGraph(optimization->GetPassName());
+    optimization->Check();
   }
 }
 
@@ -271,11 +282,6 @@
       && CanOptimize(*code_item)
       && RegisterAllocator::CanAllocateRegistersFor(*graph, instruction_set)) {
     optimized_compiled_methods_++;
-    graph->BuildDominatorTree();
-    graph->TransformToSSA();
-    visualizer.DumpGraph("ssa");
-    graph->FindNaturalLoops();
-
     RunOptimizations(graph, visualizer);
 
     PrepareForRegisterAllocation(graph).Run();
@@ -321,7 +327,7 @@
       graph->FindNaturalLoops();
       SsaRedundantPhiElimination(graph).Run();
       SsaDeadPhiElimination(graph).Run();
-      GlobalValueNumberer(graph->GetArena(), graph).Run();
+      GVNOptimization(graph).Run();
       SsaLivenessAnalysis liveness(*graph, codegen);
       liveness.Analyze();
       visualizer.DumpGraph(kLivenessPassName);
diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index b2cc119..edfafcd 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -18,6 +18,7 @@
 
 #include "nodes.h"
 #include "ssa_type_propagation.h"
+#include "ssa_phi_elimination.h"
 
 namespace art {
 
@@ -41,11 +42,20 @@
     }
   }
 
-  // 3) Propagate types of phis.
+  // 3) Remove dead phis. This will remove phis that are only used by environments:
+  // at the DEX level, the type of these phis does not need to be consistent, but
+  // our code generator will complain if the inputs of a phi do not have the same
+  // type (modulo the special case of `null`).
+  SsaDeadPhiElimination dead_phis(GetGraph());
+  dead_phis.Run();
+
+  // 4) Propagate types of phis. At this point, phis are typed void in the general
+  // case, or float or double when we created a floating-point equivalent. So we
+  // need to propagate the types across phis to give them a correct type.
   SsaTypePropagation type_propagation(GetGraph());
   type_propagation.Run();
 
-  // 4) Clear locals.
+  // 5) Clear locals.
   // TODO: Move this to a dead code eliminator phase.
   for (HInstructionIterator it(GetGraph()->GetEntryBlock()->GetInstructions());
        !it.Done();
diff --git a/compiler/optimizing/ssa_builder.h b/compiler/optimizing/ssa_builder.h
index 2207cd6..5ab328f 100644
--- a/compiler/optimizing/ssa_builder.h
+++ b/compiler/optimizing/ssa_builder.h
@@ -18,9 +18,24 @@
 #define ART_COMPILER_OPTIMIZING_SSA_BUILDER_H_
 
 #include "nodes.h"
+#include "optimization.h"
 
 namespace art {
 
+class TransformToSsa : public HOptimization {
+ public:
+  explicit TransformToSsa(HGraph* graph) : HOptimization(graph, true, "ssa transform") {}
+
+  void Run() OVERRIDE {
+    graph_->BuildDominatorTree();
+    graph_->TransformToSSA();
+    graph_->FindNaturalLoops();
+  }
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(TransformToSsa);
+};
+
 static constexpr int kDefaultNumberOfLoops = 2;
 
 class SsaBuilder : public HGraphVisitor {
diff --git a/compiler/optimizing/ssa_phi_elimination.cc b/compiler/optimizing/ssa_phi_elimination.cc
index 56979e1..58cea77 100644
--- a/compiler/optimizing/ssa_phi_elimination.cc
+++ b/compiler/optimizing/ssa_phi_elimination.cc
@@ -24,6 +24,8 @@
     HBasicBlock* block = it.Current();
     for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) {
       HPhi* phi = inst_it.Current()->AsPhi();
+      // Set dead ahead of running through uses. The phi may have no use.
+      phi->SetDead();
       for (HUseIterator<HInstruction> use_it(phi->GetUses()); !use_it.Done(); use_it.Advance()) {
         HUseListNode<HInstruction>* current = use_it.Current();
         HInstruction* user = current->GetUser();
@@ -31,8 +33,6 @@
           worklist_.Add(phi);
           phi->SetLive();
           break;
-        } else {
-          phi->SetDead();
         }
       }
     }
@@ -65,8 +65,8 @@
                use_it.Advance()) {
             HUseListNode<HInstruction>* user_node = use_it.Current();
             HInstruction* user = user_node->GetUser();
-            DCHECK(user->IsLoopHeaderPhi());
-            DCHECK(user->AsPhi()->IsDead());
+            DCHECK(user->IsLoopHeaderPhi()) << user->GetId();
+            DCHECK(user->AsPhi()->IsDead()) << user->GetId();
             // Just put itself as an input. The phi will be removed in this loop anyway.
             user->SetRawInputAt(user_node->GetIndex(), user);
             current->RemoveUser(user, user_node->GetIndex());
diff --git a/test/431-type-propagation/expected.txt b/test/431-type-propagation/expected.txt
new file mode 100644
index 0000000..ccaf6f8
--- /dev/null
+++ b/test/431-type-propagation/expected.txt
@@ -0,0 +1 @@
+Enter
diff --git a/test/431-type-propagation/info.txt b/test/431-type-propagation/info.txt
new file mode 100644
index 0000000..b895e91
--- /dev/null
+++ b/test/431-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/431-type-propagation/smali/TypePropagation.smali b/test/431-type-propagation/smali/TypePropagation.smali
new file mode 100644
index 0000000..817f0c5
--- /dev/null
+++ b/test/431-type-propagation/smali/TypePropagation.smali
@@ -0,0 +1,43 @@
+# Copyright (C) 2014 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 3
+   const/4 v0, 0
+   aget v1, v2, v0
+   add-int v2, v1, v0
+   if-eq v1, v0, :end
+   # Putting a float in v1 will lead to the creation of a phi with one
+   # float input and one integer input. Since the SSA builder trusts
+   # the verifier, it assumes that the integer input must be converted
+   # to float. However, since v0 is not used afterwards, the verifier
+   # hasn't ensured that. Therefore, the compiler must remove
+   # the phi prior to doing type propagation.
+   int-to-float v1, v0
+   :end
+   # Do a call to create an environment that will capture all Dex registers.
+   # This environment is the reason why a phi is created at the join block
+   # of the if.
+   invoke-static {}, LTypePropagation;->emptyMethod()V
+   return-void
+.end method
+
+.method public static emptyMethod()V
+   .registers 0
+   return-void
+.end method
diff --git a/test/431-type-propagation/src/Main.java b/test/431-type-propagation/src/Main.java
new file mode 100644
index 0000000..91dfe10
--- /dev/null
+++ b/test/431-type-propagation/src/Main.java
@@ -0,0 +1,28 @@
+/*
+ * Copyright (C) 2014 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 {
+    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);
+  }
+}