diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 0f2c1cf..1995797 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -4238,7 +4238,7 @@
         inputs_(number_of_inputs, arena->Adapter(kArenaAllocPhiInputs)),
         reg_number_(reg_number),
         type_(type),
-        is_live_(false),
+        is_live_(true),
         can_be_null_(true) {
   }
 
@@ -4263,7 +4263,18 @@
   void RemoveInputAt(size_t index);
 
   Primitive::Type GetType() const OVERRIDE { return type_; }
-  void SetType(Primitive::Type type) { type_ = type; }
+  void SetType(Primitive::Type new_type) {
+    // Make sure that only valid type changes occur. The following are allowed:
+    //  (1) void -> * (initial type assignment),
+    //  (2) int  -> float/ref (primitive type propagation),
+    //  (3) long -> double (primitive type propagation).
+    DCHECK(type_ == new_type ||
+           type_ == Primitive::kPrimVoid ||
+           (type_ == Primitive::kPrimInt && new_type == Primitive::kPrimFloat) ||
+           (type_ == Primitive::kPrimInt && new_type == Primitive::kPrimNot) ||
+           (type_ == Primitive::kPrimLong && new_type == Primitive::kPrimDouble));
+    type_ = new_type;
+  }
 
   bool CanBeNull() const OVERRIDE { return can_be_null_; }
   void SetCanBeNull(bool can_be_null) { can_be_null_ = can_be_null; }
@@ -4485,7 +4496,8 @@
             SideEffects additional_side_effects = SideEffects::None())
       : HExpression(type,
                     SideEffects::ArrayReadOfType(type).Union(additional_side_effects),
-                    dex_pc) {
+                    dex_pc),
+        fixed_type_(type != Primitive::kPrimInt && type != Primitive::kPrimLong) {
     SetRawInputAt(0, array);
     SetRawInputAt(1, index);
   }
@@ -4503,7 +4515,13 @@
     return false;
   }
 
-  void SetType(Primitive::Type type) { type_ = type; }
+  void SetType(Primitive::Type type) {
+    DCHECK(type_ == type || !IsTypeFixed());
+    type_ = type;
+  }
+
+  bool IsTypeFixed() const { return fixed_type_; }
+  void FixType() { fixed_type_ = true; }
 
   HInstruction* GetArray() const { return InputAt(0); }
   HInstruction* GetIndex() const { return InputAt(1); }
@@ -4511,6 +4529,12 @@
   DECLARE_INSTRUCTION(ArrayGet);
 
  private:
+  // Bytecode aget(-wide) instructions have ambiguous type (int/float, long/double).
+  // If the type can be determined from uses, `fixed_type_` should be set to true,
+  // to prevent PrimitiveTypePropagation from changing it while typing phis. With
+  // other aget-* variants, the type is always unambiguous.
+  bool fixed_type_;
+
   DISALLOW_COPY_AND_ASSIGN(HArrayGet);
 };
 
diff --git a/compiler/optimizing/primitive_type_propagation.cc b/compiler/optimizing/primitive_type_propagation.cc
index c98f43e..c38f466 100644
--- a/compiler/optimizing/primitive_type_propagation.cc
+++ b/compiler/optimizing/primitive_type_propagation.cc
@@ -21,60 +21,120 @@
 
 namespace art {
 
-static Primitive::Type MergeTypes(Primitive::Type existing, Primitive::Type new_type) {
-  // We trust the verifier has already done the necessary checking.
-  switch (existing) {
-    case Primitive::kPrimFloat:
-    case Primitive::kPrimDouble:
-    case Primitive::kPrimNot:
-      return existing;
-    default:
-      // Phis are initialized with a void type, so if we are asked
-      // to merge with a void type, we should use the existing one.
-      return new_type == Primitive::kPrimVoid
-          ? existing
-          : HPhi::ToPhiType(new_type);
+bool PrimitiveTypePropagation::TypePhiFromInputs(HPhi* phi) {
+  Primitive::Type common_type = phi->GetType();
+
+  for (HInputIterator it(phi); !it.Done(); it.Advance()) {
+    HInstruction* input = it.Current();
+    if (input->IsPhi() && input->AsPhi()->IsDead()) {
+      // Phis are constructed live so if an input is a dead phi, it must have
+      // been made dead due to type conflict. Mark this phi conflicting too.
+      return false;
+    }
+
+    Primitive::Type input_type = HPhi::ToPhiType(input->GetType());
+    if (common_type == Primitive::kPrimVoid) {
+      // Setting type for the first time.
+      common_type = input_type;
+    } else if (common_type == input_type) {
+      // No change in type.
+    } else if (input_type == Primitive::kPrimVoid) {
+      // Input is a phi which has not been typed yet. Do nothing.
+      DCHECK(input->IsPhi());
+    } else if (Primitive::ComponentSize(common_type) != Primitive::ComponentSize(input_type)) {
+      // Types are of different sizes, e.g. int vs. long. Must be a conflict.
+      return false;
+    } else if (Primitive::IsIntegralType(common_type)) {
+      // Previous inputs were integral, this one is not but is of the same size.
+      // This does not imply conflict since some bytecode instruction types are
+      // ambiguous. TypeInputsOfPhi will either type them or detect a conflict.
+      DCHECK(Primitive::IsFloatingPointType(input_type) || input_type == Primitive::kPrimNot);
+      common_type = input_type;
+    } else if (Primitive::IsIntegralType(input_type)) {
+      // Input is integral, common type is not. Same as in the previous case, if
+      // there is a conflict, it will be detected during TypeInputsOfPhi.
+      DCHECK(Primitive::IsFloatingPointType(common_type) || common_type == Primitive::kPrimNot);
+    } else {
+      // Combining float and reference types. Clearly a conflict.
+      DCHECK((common_type == Primitive::kPrimFloat && input_type == Primitive::kPrimNot) ||
+             (common_type == Primitive::kPrimNot && input_type == Primitive::kPrimFloat));
+      return false;
+    }
   }
+
+  // We have found a candidate type for the phi. Set it and return true. We may
+  // still discover conflict whilst typing the individual inputs in TypeInputsOfPhi.
+  phi->SetType(common_type);
+  return true;
 }
 
-// Re-compute and update the type of the instruction. Returns
-// whether or not the type was changed.
-bool PrimitiveTypePropagation::UpdateType(HPhi* phi) {
-  DCHECK(phi->IsLive());
-  Primitive::Type existing = phi->GetType();
-
-  Primitive::Type new_type = existing;
-  for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
-    Primitive::Type input_type = phi->InputAt(i)->GetType();
-    new_type = MergeTypes(new_type, input_type);
-  }
-  phi->SetType(new_type);
-
-  if (new_type == Primitive::kPrimDouble
-      || new_type == Primitive::kPrimFloat
-      || new_type == Primitive::kPrimNot) {
-    // If the phi is of floating point type, we need to update its inputs to that
-    // type. For inputs that are phis, we need to recompute their types.
+bool PrimitiveTypePropagation::TypeInputsOfPhi(HPhi* phi) {
+  Primitive::Type common_type = phi->GetType();
+  if (common_type == Primitive::kPrimVoid || Primitive::IsIntegralType(common_type)) {
+    // Phi either contains only other untyped phis (common_type == kPrimVoid),
+    // or `common_type` is integral and we do not need to retype ambiguous inputs
+    // because they are always constructed with the integral type candidate.
+    if (kIsDebugBuild) {
+      for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
+        HInstruction* input = phi->InputAt(i);
+        if (common_type == Primitive::kPrimVoid) {
+          DCHECK(input->IsPhi() && input->GetType() == Primitive::kPrimVoid);
+        } else {
+          DCHECK((input->IsPhi() && input->GetType() == Primitive::kPrimVoid) ||
+                 HPhi::ToPhiType(input->GetType()) == common_type);
+        }
+      }
+    }
+    // Inputs did not need to be replaced, hence no conflict. Report success.
+    return true;
+  } else {
+    DCHECK(common_type == Primitive::kPrimNot || Primitive::IsFloatingPointType(common_type));
     for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
       HInstruction* input = phi->InputAt(i);
-      if (input->GetType() != new_type) {
-        HInstruction* equivalent = (new_type == Primitive::kPrimNot)
+      if (input->GetType() != common_type) {
+        // Input type does not match phi's type. Try to retype the input or
+        // generate a suitably typed equivalent.
+        HInstruction* equivalent = (common_type == Primitive::kPrimNot)
             ? SsaBuilder::GetReferenceTypeEquivalent(input)
-            : SsaBuilder::GetFloatOrDoubleEquivalent(phi, input, new_type);
+            : SsaBuilder::GetFloatOrDoubleEquivalent(phi, input, common_type);
+        if (equivalent == nullptr) {
+          // Input could not be typed. Report conflict.
+          return false;
+        }
+
         phi->ReplaceInput(equivalent, i);
         if (equivalent->IsPhi()) {
-          equivalent->AsPhi()->SetLive();
           AddToWorklist(equivalent->AsPhi());
         } else if (equivalent == input) {
           // The input has changed its type. It can be an input of other phis,
           // so we need to put phi users in the work list.
-          AddDependentInstructionsToWorklist(equivalent);
+          AddDependentInstructionsToWorklist(input);
         }
       }
     }
+    // All inputs either matched the type of the phi or we successfully replaced
+    // them with a suitable equivalent. Report success.
+    return true;
+  }
+}
+
+bool PrimitiveTypePropagation::UpdateType(HPhi* phi) {
+  DCHECK(phi->IsLive());
+  Primitive::Type original_type = phi->GetType();
+
+  // Try to type the phi in two stages:
+  // (1) find a candidate type for the phi by merging types of all its inputs,
+  // (2) try to type the phi's inputs to that candidate type.
+  // Either of these stages may detect a type conflict and fail, in which case
+  // we immediately abort.
+  if (!TypePhiFromInputs(phi) || !TypeInputsOfPhi(phi)) {
+    // Conflict detected. Mark the phi dead and return true because it changed.
+    phi->SetDead();
+    return true;
   }
 
-  return existing != new_type;
+  // Return true if the type of the phi has changed.
+  return phi->GetType() != original_type;
 }
 
 void PrimitiveTypePropagation::Run() {
@@ -109,10 +169,12 @@
 
 void PrimitiveTypePropagation::ProcessWorklist() {
   while (!worklist_.empty()) {
-    HPhi* instruction = worklist_.back();
+    HPhi* phi = worklist_.back();
     worklist_.pop_back();
-    if (UpdateType(instruction)) {
-      AddDependentInstructionsToWorklist(instruction);
+    // The phi could have been made dead as a result of conflicts while in the
+    // worklist. If it is now dead, there is no point in updating its type.
+    if (phi->IsLive() && UpdateType(phi)) {
+      AddDependentInstructionsToWorklist(phi);
     }
   }
 }
@@ -123,10 +185,17 @@
 }
 
 void PrimitiveTypePropagation::AddDependentInstructionsToWorklist(HInstruction* instruction) {
+  // If `instruction` is a dead phi, type conflict was just identified. All its
+  // live phi users, and transitively users of those users, therefore need to be
+  // marked dead/conflicting too, so we add them to the worklist. Otherwise we
+  // add users whose type does not match and needs to be updated.
+  bool add_all_live_phis = instruction->IsPhi() && instruction->AsPhi()->IsDead();
   for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) {
-    HPhi* phi = it.Current()->GetUser()->AsPhi();
-    if (phi != nullptr && phi->IsLive() && phi->GetType() != instruction->GetType()) {
-      AddToWorklist(phi);
+    HInstruction* user = it.Current()->GetUser();
+    if (user->IsPhi() && user->AsPhi()->IsLive()) {
+      if (add_all_live_phis || user->GetType() != instruction->GetType()) {
+        AddToWorklist(user->AsPhi());
+      }
     }
   }
 }
diff --git a/compiler/optimizing/primitive_type_propagation.h b/compiler/optimizing/primitive_type_propagation.h
index 212fcfc..0b69483 100644
--- a/compiler/optimizing/primitive_type_propagation.h
+++ b/compiler/optimizing/primitive_type_propagation.h
@@ -38,6 +38,8 @@
   void AddToWorklist(HPhi* phi);
   void AddDependentInstructionsToWorklist(HInstruction* instruction);
   bool UpdateType(HPhi* phi);
+  bool TypePhiFromInputs(HPhi* phi);
+  bool TypeInputsOfPhi(HPhi* phi);
 
   HGraph* const graph_;
   ArenaVector<HPhi*> worklist_;
diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index 4565590..20a8bdb 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -22,204 +22,18 @@
 
 namespace art {
 
-/**
- * A debuggable application may require to reviving phis, to ensure their
- * associated DEX register is available to a debugger. This class implements
- * the logic for statement (c) of the SsaBuilder (see ssa_builder.h). It
- * also makes sure that phis with incompatible input types are not revived
- * (statement (b) of the SsaBuilder).
- *
- * This phase must be run after detecting dead phis through the
- * DeadPhiElimination phase, and before deleting the dead phis.
- */
-class DeadPhiHandling : public ValueObject {
- public:
-  explicit DeadPhiHandling(HGraph* graph)
-      : graph_(graph), worklist_(graph->GetArena()->Adapter(kArenaAllocSsaBuilder)) {
-    worklist_.reserve(kDefaultWorklistSize);
-  }
-
-  void Run();
-
- private:
-  void VisitBasicBlock(HBasicBlock* block);
-  void ProcessWorklist();
-  void AddToWorklist(HPhi* phi);
-  void AddDependentInstructionsToWorklist(HPhi* phi);
-  bool UpdateType(HPhi* phi);
-
-  HGraph* const graph_;
-  ArenaVector<HPhi*> worklist_;
-
-  static constexpr size_t kDefaultWorklistSize = 8;
-
-  DISALLOW_COPY_AND_ASSIGN(DeadPhiHandling);
-};
-
-static bool HasConflictingEquivalent(HPhi* phi) {
-  if (phi->GetNext() == nullptr) {
-    return false;
-  }
-  HPhi* next = phi->GetNext()->AsPhi();
-  if (next->GetRegNumber() == phi->GetRegNumber()) {
-    if (next->GetType() == Primitive::kPrimVoid) {
-      // We only get a void type for an equivalent phi we processed and found out
-      // it was conflicting.
-      return true;
-    } else {
-      // Go to the next phi, in case it is also an equivalent.
-      return HasConflictingEquivalent(next);
-    }
-  }
-  return false;
-}
-
-bool DeadPhiHandling::UpdateType(HPhi* phi) {
-  if (phi->IsDead()) {
-    // Phi was rendered dead while waiting in the worklist because it was replaced
-    // with an equivalent.
-    return false;
-  }
-
-  Primitive::Type existing = phi->GetType();
-
-  bool conflict = false;
-  Primitive::Type new_type = existing;
-  for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
-    HInstruction* input = phi->InputAt(i);
-    if (input->IsPhi() && input->AsPhi()->IsDead()) {
-      // We are doing a reverse post order visit of the graph, reviving
-      // phis that have environment uses and updating their types. If an
-      // input is a phi, and it is dead (because its input types are
-      // conflicting), this phi must be marked dead as well.
-      conflict = true;
-      break;
-    }
-    Primitive::Type input_type = HPhi::ToPhiType(input->GetType());
-
-    // The only acceptable transitions are:
-    // - From void to typed: first time we update the type of this phi.
-    // - From int to reference (or reference to int): the phi has to change
-    //   to reference type. If the integer input cannot be converted to a
-    //   reference input, the phi will remain dead.
-    if (new_type == Primitive::kPrimVoid) {
-      new_type = input_type;
-    } else if (new_type == Primitive::kPrimNot && input_type == Primitive::kPrimInt) {
-      if (input->IsPhi() && HasConflictingEquivalent(input->AsPhi())) {
-        // If we already asked for an equivalent of the input phi, but that equivalent
-        // ended up conflicting, make this phi conflicting too.
-        conflict = true;
-        break;
-      }
-      HInstruction* equivalent = SsaBuilder::GetReferenceTypeEquivalent(input);
-      if (equivalent == nullptr) {
-        conflict = true;
-        break;
-      }
-      phi->ReplaceInput(equivalent, i);
-      if (equivalent->IsPhi()) {
-        DCHECK_EQ(equivalent->GetType(), Primitive::kPrimNot);
-        // We created a new phi, but that phi has the same inputs as the old phi. We
-        // add it to the worklist to ensure its inputs can also be converted to reference.
-        // If not, it will remain dead, and the algorithm will make the current phi dead
-        // as well.
-        equivalent->AsPhi()->SetLive();
-        AddToWorklist(equivalent->AsPhi());
-      }
-    } else if (new_type == Primitive::kPrimInt && input_type == Primitive::kPrimNot) {
-      new_type = Primitive::kPrimNot;
-      // Start over, we may request reference equivalents for the inputs of the phi.
-      i = -1;
-    } else if (new_type != input_type) {
-      conflict = true;
-      break;
-    }
-  }
-
-  if (conflict) {
-    phi->SetType(Primitive::kPrimVoid);
-    phi->SetDead();
-    return true;
-  } else if (existing == new_type) {
-    return false;
-  }
-
-  DCHECK(phi->IsLive());
-  phi->SetType(new_type);
-
-  // There might exist a `new_type` equivalent of `phi` already. In that case,
-  // we replace the equivalent with the, now live, `phi`.
-  HPhi* equivalent = phi->GetNextEquivalentPhiWithSameType();
-  if (equivalent != nullptr) {
-    // There cannot be more than two equivalents with the same type.
-    DCHECK(equivalent->GetNextEquivalentPhiWithSameType() == nullptr);
-    // If doing fix-point iteration, the equivalent might be in `worklist_`.
-    // Setting it dead will make UpdateType skip it.
-    equivalent->SetDead();
-    equivalent->ReplaceWith(phi);
-  }
-
-  return true;
-}
-
-void DeadPhiHandling::VisitBasicBlock(HBasicBlock* block) {
-  for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
-    HPhi* phi = it.Current()->AsPhi();
-    if (phi->IsDead() && phi->HasEnvironmentUses()) {
-      phi->SetLive();
-      if (block->IsLoopHeader()) {
-        // Give a type to the loop phi to guarantee convergence of the algorithm.
-        // Note that the dead phi may already have a type if it is an equivalent
-        // generated for a typed LoadLocal. In that case we do not change the
-        // type because it could lead to an unsupported PrimNot/Float/Double ->
-        // PrimInt/Long transition and create same type equivalents.
-        if (phi->GetType() == Primitive::kPrimVoid) {
-          phi->SetType(phi->InputAt(0)->GetType());
-        }
-        AddToWorklist(phi);
-      } else {
-        // Because we are doing a reverse post order visit, all inputs of
-        // this phi have been visited and therefore had their (initial) type set.
-        UpdateType(phi);
+void SsaBuilder::SetLoopPhiInputs() {
+  for (HBasicBlock* block : loop_headers_) {
+    for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
+      HPhi* phi = it.Current()->AsPhi();
+      for (HBasicBlock* predecessor : block->GetPredecessors()) {
+        HInstruction* input = ValueOfLocal(predecessor, phi->GetRegNumber());
+        phi->AddInput(input);
       }
     }
   }
 }
 
-void DeadPhiHandling::ProcessWorklist() {
-  while (!worklist_.empty()) {
-    HPhi* instruction = worklist_.back();
-    worklist_.pop_back();
-    // Note that the same equivalent phi can be added multiple times in the work list, if
-    // used by multiple phis. The first call to `UpdateType` will know whether the phi is
-    // dead or live.
-    if (instruction->IsLive() && UpdateType(instruction)) {
-      AddDependentInstructionsToWorklist(instruction);
-    }
-  }
-}
-
-void DeadPhiHandling::AddToWorklist(HPhi* instruction) {
-  DCHECK(instruction->IsLive());
-  worklist_.push_back(instruction);
-}
-
-void DeadPhiHandling::AddDependentInstructionsToWorklist(HPhi* instruction) {
-  for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) {
-    HPhi* phi = it.Current()->GetUser()->AsPhi();
-    if (phi != nullptr && !phi->IsDead()) {
-      AddToWorklist(phi);
-    }
-  }
-}
-
-void DeadPhiHandling::Run() {
-  for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
-    VisitBasicBlock(it.Current());
-  }
-  ProcessWorklist();
-}
-
 void SsaBuilder::FixNullConstantType() {
   // The order doesn't matter here.
   for (HReversePostOrderIterator itb(*GetGraph()); !itb.Done(); itb.Advance()) {
@@ -259,10 +73,11 @@
       HPhi* phi = it.Current()->AsPhi();
       HPhi* next = phi->GetNextEquivalentPhiWithSameType();
       if (next != nullptr) {
-        // Make sure we do not replace a live phi with a dead phi. A live phi has been
-        // handled by the type propagation phase, unlike a dead phi.
+        // Make sure we do not replace a live phi with a dead phi. A live phi
+        // has been handled by the type propagation phase, unlike a dead phi.
         if (next->IsLive()) {
           phi->ReplaceWith(next);
+          phi->SetDead();
         } else {
           next->ReplaceWith(phi);
         }
@@ -274,72 +89,7 @@
   }
 }
 
-void SsaBuilder::BuildSsa() {
-  // 1) Visit in reverse post order. We need to have all predecessors of a block visited
-  // (with the exception of loops) in order to create the right environment for that
-  // block. For loops, we create phis whose inputs will be set in 2).
-  for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) {
-    VisitBasicBlock(it.Current());
-  }
-
-  // 2) Set inputs of loop phis.
-  for (HBasicBlock* block : loop_headers_) {
-    for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
-      HPhi* phi = it.Current()->AsPhi();
-      for (HBasicBlock* predecessor : block->GetPredecessors()) {
-        HInstruction* input = ValueOfLocal(predecessor, phi->GetRegNumber());
-        phi->AddInput(input);
-      }
-    }
-  }
-
-  // 3) Mark dead phis. This will mark 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. The marking allows the type propagation to know which phis it needs
-  // to handle. We mark but do not eliminate: the elimination will be done in
-  // step 9).
-  SsaDeadPhiElimination dead_phis_for_type_propagation(GetGraph());
-  dead_phis_for_type_propagation.MarkDeadPhis();
-
-  // 4) Propagate types of phis. At this point, phis are typed void in the general
-  // case, or float/double/reference when we created an equivalent phi. So we
-  // need to propagate the types across phis to give them a correct type.
-  PrimitiveTypePropagation type_propagation(GetGraph());
-  type_propagation.Run();
-
-  // 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();
-
-  // 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();
-
-  // 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
-  // SsaBuilder (see ssa_builder.h).
-  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
-  // can be multiple phis for the same Dex register that are live (for example
-  // when merging constants), in which case it is OK for the environments
-  // to just reference one.
+void SsaBuilder::FixEnvironmentPhis() {
   for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) {
     HBasicBlock* block = it.Current();
     for (HInstructionIterator it_phis(block->GetPhis()); !it_phis.Done(); it_phis.Advance()) {
@@ -360,24 +110,68 @@
       phi->ReplaceWith(next);
     }
   }
+}
 
-  // 10) Deal with phis to guarantee liveness of phis in case of a debuggable
-  // application. This is for satisfying statement (c) of the SsaBuilder
-  // (see ssa_builder.h).
-  if (GetGraph()->IsDebuggable()) {
-    DeadPhiHandling dead_phi_handler(GetGraph());
-    dead_phi_handler.Run();
+void SsaBuilder::BuildSsa() {
+  // 1) Visit in reverse post order. We need to have all predecessors of a block visited
+  // (with the exception of loops) in order to create the right environment for that
+  // block. For loops, we create phis whose inputs will be set in 2).
+  for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) {
+    VisitBasicBlock(it.Current());
   }
 
-  // 11) Now that the right phis are used for the environments, and we
-  // have potentially revive dead phis in case of a debuggable application,
-  // we can eliminate phis we do not need. Regardless of the debuggable status,
-  // this phase is necessary for statement (b) of the SsaBuilder (see ssa_builder.h),
-  // as well as for the code generation, which does not deal with phis of conflicting
+  // 2) Set inputs of loop phis.
+  SetLoopPhiInputs();
+
+  // 3) Propagate types of phis. At this point, phis are typed void in the general
+  // case, or float/double/reference if we created an equivalent phi. So we need
+  // to propagate the types across phis to give them a correct type. If a type
+  // conflict is detected in this stage, the phi is marked dead.
+  PrimitiveTypePropagation(GetGraph()).Run();
+
+  // 4) 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();
+
+  // 5) Mark dead phis. This will mark phis which are not used by instructions or
+  // other live phis. If compiling as debuggable code, phis will also be kept live
+  // if they have an environment use.
+  SsaDeadPhiElimination dead_phis(GetGraph());
+  dead_phis.MarkDeadPhis();
+
+  // 6) Make sure environments use the right phi equivalent: a phi marked dead
+  // can have a phi equivalent that is not dead. In that case we have to replace
+  // it with the live equivalent because deoptimization and try/catch rely on
+  // environments containing values of all live vregs at that point. Note that
+  // there can be multiple phis for the same Dex register that are live
+  // (for example when merging constants), in which case it is okay for the
+  // environments to just reference one.
+  FixEnvironmentPhis();
+
+  // 7) Now that the right phis are used for the environments, we can eliminate
+  // phis we do not need. Regardless of the debuggable status, this phase is
+  /// necessary for statement (b) of the SsaBuilder (see ssa_builder.h), as well
+  // as for the code generation, which does not deal with phis of conflicting
   // input types.
   dead_phis.EliminateDeadPhis();
 
-  // 12) Clear locals.
+  // 8) 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
+  // SsaBuilder (see ssa_builder.h).
+  SsaRedundantPhiElimination(GetGraph()).Run();
+
+  // 9) 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();
+
+  // 10) Clear locals.
   for (HInstructionIterator it(GetGraph()->GetEntryBlock()->GetInstructions());
        !it.Done();
        it.Advance()) {
@@ -561,6 +355,8 @@
  * phi with a floating point / reference type.
  */
 HPhi* SsaBuilder::GetFloatDoubleOrReferenceEquivalentOfPhi(HPhi* phi, Primitive::Type type) {
+  DCHECK(phi->IsLive()) << "Cannot get equivalent of a dead phi since it would create a live one.";
+
   // We place the floating point /reference phi next to this phi.
   HInstruction* next = phi->GetNext();
   if (next != nullptr
@@ -576,15 +372,18 @@
     ArenaAllocator* allocator = phi->GetBlock()->GetGraph()->GetArena();
     HPhi* new_phi = new (allocator) HPhi(allocator, phi->GetRegNumber(), phi->InputCount(), type);
     for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
-      // Copy the inputs. Note that the graph may not be correctly typed by doing this copy,
-      // but the type propagation phase will fix it.
+      // Copy the inputs. Note that the graph may not be correctly typed
+      // by doing this copy, but the type propagation phase will fix it.
       new_phi->SetRawInputAt(i, phi->InputAt(i));
     }
     phi->GetBlock()->InsertPhiAfter(new_phi, phi);
+    DCHECK(new_phi->IsLive());
     return new_phi;
   } else {
     DCHECK_EQ(next->GetType(), type);
-    return next->AsPhi();
+    // An existing equivalent was found. If it is dead, conflict was previously
+    // identified and we return nullptr instead.
+    return next->AsPhi()->IsLive() ? next->AsPhi() : nullptr;
   }
 }
 
@@ -592,11 +391,15 @@
                                                      HInstruction* value,
                                                      Primitive::Type type) {
   if (value->IsArrayGet()) {
-    // The verifier has checked that values in arrays cannot be used for both
-    // floating point and non-floating point operations. It is therefore safe to just
-    // change the type of the operation.
-    value->AsArrayGet()->SetType(type);
-    return value;
+    HArrayGet* aget = value->AsArrayGet();
+    if (aget->GetType() != type && aget->IsTypeFixed()) {
+      // Requested a float/double equivalent of ArrayGet with int/long uses.
+      // Must be a phi with type conflict.
+      DCHECK(user->IsPhi());
+      return nullptr;
+    }
+    aget->SetType(type);
+    return aget;
   } else if (value->IsLongConstant()) {
     return GetDoubleEquivalent(value->AsLongConstant());
   } else if (value->IsIntConstant()) {
@@ -604,12 +407,7 @@
   } else if (value->IsPhi()) {
     return GetFloatDoubleOrReferenceEquivalentOfPhi(value->AsPhi(), type);
   } else {
-    // For other instructions, we assume the verifier has checked that the dex format is correctly
-    // typed and the value in a dex register will not be used for both floating point and
-    // non-floating point operations. So the only reason an instruction would want a floating
-    // point equivalent is for an unused phi that will be removed by the dead phi elimination phase.
-    DCHECK(user->IsPhi()) << "is actually " << user->DebugName() << " (" << user->GetId() << ")";
-    return value;
+    return nullptr;
   }
 }
 
@@ -633,6 +431,21 @@
       value = GetReferenceTypeEquivalent(value);
     }
   }
+
+  // If value is HArrayGet, check if uses of the HLoadLocal disambiguate its
+  // type between int/long and float/double.
+  if (value->IsArrayGet() && !value->AsArrayGet()->IsTypeFixed()) {
+    for (HUseIterator<HInstruction*> use_it(load->GetUses()); !use_it.Done(); use_it.Advance()) {
+      HInstruction* user = use_it.Current()->GetUser();
+      if (!user->IsStoreLocal() &&
+          !user->IsPhi() &&
+          (!user->IsArraySet() || user->AsArraySet()->GetIndex() == value)) {
+        value->AsArrayGet()->FixType();
+        break;
+      }
+    }
+  }
+
   load->ReplaceWith(value);
   load->GetBlock()->RemoveInstruction(load);
 }
diff --git a/compiler/optimizing/ssa_builder.h b/compiler/optimizing/ssa_builder.h
index 79f1a28..da0583c 100644
--- a/compiler/optimizing/ssa_builder.h
+++ b/compiler/optimizing/ssa_builder.h
@@ -81,6 +81,8 @@
   static constexpr const char* kSsaBuilderPassName = "ssa_builder";
 
  private:
+  void SetLoopPhiInputs();
+  void FixEnvironmentPhis();
   void FixNullConstantType();
   void EquivalentPhisCleanup();
 
diff --git a/compiler/optimizing/ssa_phi_elimination.cc b/compiler/optimizing/ssa_phi_elimination.cc
index 72f9ddd..c6993f3 100644
--- a/compiler/optimizing/ssa_phi_elimination.cc
+++ b/compiler/optimizing/ssa_phi_elimination.cc
@@ -29,17 +29,28 @@
     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();
-        if (!user->IsPhi()) {
-          worklist_.push_back(phi);
-          phi->SetLive();
-          break;
+      if (phi->IsDead()) {
+        // Phis are constructed live so this one was proven conflicting.
+        continue;
+      }
+
+      bool is_live = false;
+      if (graph_->IsDebuggable() && phi->HasEnvironmentUses()) {
+        is_live = true;
+      } else {
+        for (HUseIterator<HInstruction*> use_it(phi->GetUses()); !use_it.Done(); use_it.Advance()) {
+          if (!use_it.Current()->GetUser()->IsPhi()) {
+            is_live = true;
+            break;
+          }
         }
       }
+
+      if (is_live) {
+        worklist_.push_back(phi);
+      } else {
+        phi->SetDead();
+      }
     }
   }
 
@@ -50,8 +61,10 @@
     for (HInputIterator it(phi); !it.Done(); it.Advance()) {
       HInstruction* input = it.Current();
       if (input->IsPhi() && input->AsPhi()->IsDead()) {
-        worklist_.push_back(input->AsPhi());
+        // If we revive a phi it must have been live at the beginning of
+        // the pass but had no non-phi uses of its own.
         input->AsPhi()->SetLive();
+        worklist_.push_back(input->AsPhi());
       }
     }
   }
@@ -75,8 +88,8 @@
           for (HUseIterator<HInstruction*> use_it(phi->GetUses()); !use_it.Done();
                use_it.Advance()) {
             HInstruction* user = use_it.Current()->GetUser();
-            DCHECK(user->IsLoopHeaderPhi()) << user->GetId();
-            DCHECK(user->AsPhi()->IsDead()) << user->GetId();
+            DCHECK(user->IsPhi());
+            DCHECK(user->AsPhi()->IsDead());
           }
         }
         // Remove the phi from use lists of its inputs.
diff --git a/test/538-checker-typeprop-debuggable/expected.txt b/test/538-checker-typeprop-debuggable/expected.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/538-checker-typeprop-debuggable/expected.txt
diff --git a/test/538-checker-typeprop-debuggable/info.txt b/test/538-checker-typeprop-debuggable/info.txt
new file mode 100644
index 0000000..9d69056
--- /dev/null
+++ b/test/538-checker-typeprop-debuggable/info.txt
@@ -0,0 +1,2 @@
+Test that phis with environment uses which can be properly typed are kept
+in --debuggable mode.
\ No newline at end of file
diff --git a/test/538-checker-typeprop-debuggable/smali/ArrayGet.smali b/test/538-checker-typeprop-debuggable/smali/ArrayGet.smali
new file mode 100644
index 0000000..19583af
--- /dev/null
+++ b/test/538-checker-typeprop-debuggable/smali/ArrayGet.smali
@@ -0,0 +1,167 @@
+# 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 LArrayGet;
+.super Ljava/lang/Object;
+
+
+# Test phi with fixed-type ArrayGet as an input and a matching second input.
+# The phi should be typed accordingly.
+
+## CHECK-START: void ArrayGet.matchingFixedType(float[], float) ssa_builder (after)
+## CHECK-NOT: Phi
+
+## CHECK-START-DEBUGGABLE: void ArrayGet.matchingFixedType(float[], float) ssa_builder (after)
+## CHECK-DAG:  <<Arg1:f\d+>> ParameterValue
+## CHECK-DAG:  <<Aget:f\d+>> ArrayGet
+## CHECK-DAG:  {{f\d+}}      Phi [<<Aget>>,<<Arg1>>] reg:0
+.method public static matchingFixedType([FF)V
+  .registers 8
+
+  const v0, 0x0
+  const v1, 0x1
+
+  aget v0, p0, v0       # read value
+  add-float v2, v0, v1  # float use fixes type
+
+  float-to-int v2, p1
+  if-eqz v2, :after
+  move v0, p1
+  :after
+  # v0 = Phi [ArrayGet, Arg1] => float
+
+  invoke-static {}, Ljava/lang/System;->nanoTime()J  # create an env use
+  return-void
+.end method
+
+
+# Test phi with fixed-type ArrayGet as an input and a conflicting second input.
+# The phi should be eliminated due to the conflict.
+
+## CHECK-START: void ArrayGet.conflictingFixedType(float[], int) ssa_builder (after)
+## CHECK-NOT: Phi
+
+## CHECK-START-DEBUGGABLE: void ArrayGet.conflictingFixedType(float[], int) ssa_builder (after)
+## CHECK-NOT: Phi
+.method public static conflictingFixedType([FI)V
+  .registers 8
+
+  const v0, 0x0
+  const v1, 0x1
+
+  aget v0, p0, v0       # read value
+  add-float v2, v0, v1  # float use fixes type
+
+  if-eqz p1, :after
+  move v0, p1
+  :after
+  # v0 = Phi [ArrayGet, Arg1] => conflict
+
+  invoke-static {}, Ljava/lang/System;->nanoTime()J  # create an env use
+  return-void
+.end method
+
+
+# Same test as the one above, only this time tests that type of ArrayGet is not
+# changed.
+
+## CHECK-START: void ArrayGet.conflictingFixedType2(int[], float) ssa_builder (after)
+## CHECK-NOT: Phi
+
+## CHECK-START-DEBUGGABLE: void ArrayGet.conflictingFixedType2(int[], float) ssa_builder (after)
+## CHECK-NOT: Phi
+
+## CHECK-START-DEBUGGABLE: void ArrayGet.conflictingFixedType2(int[], float) ssa_builder (after)
+## CHECK:     {{i\d+}} ArrayGet
+.method public static conflictingFixedType2([IF)V
+  .registers 8
+
+  const v0, 0x0
+  const v1, 0x1
+
+  aget v0, p0, v0       # read value
+  add-int v2, v0, v1    # int use fixes type
+
+  float-to-int v2, p1
+  if-eqz v2, :after
+  move v0, p1
+  :after
+  # v0 = Phi [ArrayGet, Arg1] => conflict
+
+  invoke-static {}, Ljava/lang/System;->nanoTime()J  # create an env use
+  return-void
+.end method
+
+
+# Test phi with free-type ArrayGet as an input and a matching second input.
+# The phi should be typed accordingly.
+
+## CHECK-START: void ArrayGet.matchingFreeType(float[], float) ssa_builder (after)
+## CHECK-NOT: Phi
+
+## CHECK-START-DEBUGGABLE: void ArrayGet.matchingFreeType(float[], float) ssa_builder (after)
+## CHECK-DAG:  <<Arg1:f\d+>> ParameterValue
+## CHECK-DAG:  <<Aget:f\d+>> ArrayGet
+## CHECK-DAG:                ArraySet [{{l\d+}},{{i\d+}},<<Aget>>]
+## CHECK-DAG:  {{f\d+}}      Phi [<<Aget>>,<<Arg1>>] reg:0
+.method public static matchingFreeType([FF)V
+  .registers 8
+
+  const v0, 0x0
+  const v1, 0x1
+
+  aget v0, p0, v0       # read value, should be float but has no typed use
+  aput v0, p0, v1       # aput does not disambiguate the type
+
+  float-to-int v2, p1
+  if-eqz v2, :after
+  move v0, p1
+  :after
+  # v0 = Phi [ArrayGet, Arg1] => float
+
+  invoke-static {}, Ljava/lang/System;->nanoTime()J  # create an env use
+  return-void
+.end method
+
+
+# Test phi with free-type ArrayGet as an input and a conflicting second input.
+# The phi will be kept and typed according to the second input despite the
+# conflict.
+
+## CHECK-START: void ArrayGet.conflictingFreeType(int[], float) ssa_builder (after)
+## CHECK-NOT: Phi
+
+## CHECK-START-DEBUGGABLE: void ArrayGet.conflictingFreeType(int[], float) ssa_builder (after)
+## CHECK-DAG:  <<Arg1:f\d+>> ParameterValue
+## CHECK-DAG:  <<Aget:f\d+>> ArrayGet
+## CHECK-DAG:                ArraySet [{{l\d+}},{{i\d+}},<<Aget>>]
+## CHECK-DAG:  {{f\d+}}      Phi [<<Aget>>,<<Arg1>>] reg:0
+.method public static conflictingFreeType([IF)V
+  .registers 8
+
+  const v0, 0x0
+  const v1, 0x1
+
+  aget v0, p0, v0       # read value, should be int but has no typed use
+  aput v0, p0, v1       # aput does not disambiguate the type
+
+  float-to-int v2, p1
+  if-eqz v2, :after
+  move v0, p1
+  :after
+  # v0 = Phi [ArrayGet, Arg1] => float
+
+  invoke-static {}, Ljava/lang/System;->nanoTime()J  # create an env use
+  return-void
+.end method
diff --git a/test/538-checker-typeprop-debuggable/smali/SsaBuilder.smali b/test/538-checker-typeprop-debuggable/smali/SsaBuilder.smali
new file mode 100644
index 0000000..395feaa
--- /dev/null
+++ b/test/538-checker-typeprop-debuggable/smali/SsaBuilder.smali
@@ -0,0 +1,52 @@
+# 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 LSsaBuilder;
+.super Ljava/lang/Object;
+
+# Check that a dead phi with a live equivalent is replaced in an environment. The
+# following test case throws an exception and uses v0 afterwards. However, v0
+# contains a phi that is interpreted as int for the environment, and as float for
+# instruction use. SsaBuilder must substitute the int variant before removing it,
+# otherwise running the code with an array short enough to throw will crash at
+# runtime because v0 is undefined.
+
+## CHECK-START: int SsaBuilder.environmentPhi(boolean, int[]) ssa_builder (after)
+## CHECK-DAG:     <<Cst0:f\d+>>  FloatConstant 0
+## CHECK-DAG:     <<Cst2:f\d+>>  FloatConstant 2
+## CHECK-DAG:     <<Phi:f\d+>>   Phi [<<Cst0>>,<<Cst2>>]
+## CHECK-DAG:                    BoundsCheck env:[[<<Phi>>,{{i\d+}},{{z\d+}},{{l\d+}}]]
+
+.method public static environmentPhi(Z[I)I
+  .registers 4
+
+  const v0, 0x0
+  if-eqz p0, :else
+  const v0, 0x40000000
+  :else
+  # v0 = phi that can be both int and float
+
+  :try_start
+  const v1, 0x3
+  aput v1, p1, v1
+  const v0, 0x1     # generate catch phi for v0
+  const v1, 0x4
+  aput v1, p1, v1
+  :try_end
+  .catchall {:try_start .. :try_end} :use_as_float
+
+  :use_as_float
+  float-to-int v0, v0
+  return v0
+.end method
\ No newline at end of file
diff --git a/test/538-checker-typeprop-debuggable/smali/TypePropagation.smali b/test/538-checker-typeprop-debuggable/smali/TypePropagation.smali
new file mode 100644
index 0000000..58682a1
--- /dev/null
+++ b/test/538-checker-typeprop-debuggable/smali/TypePropagation.smali
@@ -0,0 +1,136 @@
+# 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;
+
+## CHECK-START-DEBUGGABLE: void TypePropagation.mergeDeadPhi(boolean, boolean, int, float, float) ssa_builder (after)
+## CHECK-NOT: Phi
+.method public static mergeDeadPhi(ZZIFF)V
+  .registers 8
+
+  if-eqz p0, :after1
+  move p2, p3
+  :after1
+  # p2 = merge(int,float) = conflict
+
+  if-eqz p1, :after2
+  move p2, p4
+  :after2
+  # p2 = merge(conflict,float) = conflict
+
+  invoke-static {}, Ljava/lang/System;->nanoTime()J  # create an env use
+  return-void
+.end method
+
+## CHECK-START-DEBUGGABLE: void TypePropagation.mergeSameType(boolean, int, int) ssa_builder (after)
+## CHECK:     {{i\d+}} Phi
+## CHECK-NOT:          Phi
+.method public static mergeSameType(ZII)V
+  .registers 8
+  if-eqz p0, :after
+  move p1, p2
+  :after
+  # p1 = merge(int,int) = int
+  invoke-static {}, Ljava/lang/System;->nanoTime()J  # create an env use
+  return-void
+.end method
+
+## CHECK-START-DEBUGGABLE: void TypePropagation.mergeVoidInput(boolean, boolean, int, int) ssa_builder (after)
+## CHECK:     {{i\d+}} Phi
+## CHECK:     {{i\d+}} Phi
+## CHECK-NOT:          Phi
+.method public static mergeVoidInput(ZZII)V
+  .registers 8
+  :loop
+  # p2 = void (loop phi) => p2 = merge(int,int) = int
+  if-eqz p0, :after
+  move p2, p3
+  :after
+  # p2 = merge(void,int) = int
+  if-eqz p1, :loop
+  invoke-static {}, Ljava/lang/System;->nanoTime()J  # create an env use
+  return-void
+.end method
+
+## CHECK-START-DEBUGGABLE: void TypePropagation.mergeDifferentSize(boolean, int, long) ssa_builder (after)
+## CHECK-NOT: Phi
+.method public static mergeDifferentSize(ZIJ)V
+  .registers 8
+  if-eqz p0, :after
+  move-wide p1, p2
+  :after
+  # p1 = merge(int,long) = conflict
+  invoke-static {}, Ljava/lang/System;->nanoTime()J  # create an env use
+  return-void
+.end method
+
+## CHECK-START-DEBUGGABLE: void TypePropagation.mergeRefFloat(boolean, float, java.lang.Object) ssa_builder (after)
+## CHECK-NOT: Phi
+.method public static mergeRefFloat(ZFLjava/lang/Object;)V
+  .registers 8
+  if-eqz p0, :after
+  move-object p1, p2
+  :after
+  # p1 = merge(float,reference) = conflict
+  invoke-static {}, Ljava/lang/System;->nanoTime()J  # create an env use
+  return-void
+.end method
+
+## CHECK-START-DEBUGGABLE: void TypePropagation.mergeIntFloat_Success(boolean, float) ssa_builder (after)
+## CHECK:     {{f\d+}} Phi
+## CHECK-NOT:          Phi
+.method public static mergeIntFloat_Success(ZF)V
+  .registers 8
+  if-eqz p0, :after
+  const/4 p1, 0x0
+  :after
+  # p1 = merge(float,0x0) = float
+  invoke-static {}, Ljava/lang/System;->nanoTime()J  # create an env use
+  return-void
+.end method
+
+## CHECK-START-DEBUGGABLE: void TypePropagation.mergeIntFloat_Fail(boolean, int, float) ssa_builder (after)
+## CHECK-NOT: Phi
+.method public static mergeIntFloat_Fail(ZIF)V
+  .registers 8
+  if-eqz p0, :after
+  move p1, p2
+  :after
+  # p1 = merge(int,float) = conflict
+  invoke-static {}, Ljava/lang/System;->nanoTime()J  # create an env use
+  return-void
+.end method
+
+## CHECK-START-DEBUGGABLE: void TypePropagation.updateAllUsersOnConflict(boolean, boolean, int, float, int) ssa_builder (after)
+## CHECK-NOT: Phi
+.method public static updateAllUsersOnConflict(ZZIFI)V
+  .registers 8
+
+  :loop1
+  # loop phis for all args
+  # p2 = merge(int,float) = float? => conflict
+  move p2, p3
+  if-eqz p0, :loop1
+
+  :loop2
+  # loop phis for all args
+  # requests float equivalent of p4 phi in loop1 => conflict
+  # propagates conflict to loop2's phis
+  move p2, p4
+  if-eqz p1, :loop2
+
+  invoke-static {}, Ljava/lang/System;->nanoTime()J  # create an env use
+  return-void
+.end method
diff --git a/test/538-checker-typeprop-debuggable/src/Main.java b/test/538-checker-typeprop-debuggable/src/Main.java
new file mode 100644
index 0000000..fe2343e
--- /dev/null
+++ b/test/538-checker-typeprop-debuggable/src/Main.java
@@ -0,0 +1,43 @@
+/*
+ * 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 {
+
+  // Workaround for b/18051191.
+  class InnerClass {}
+
+  private static void assertEquals(int expected, int actual) {
+    if (expected != actual) {
+      throw new Error("Wrong result, expected=" + expected + ", actual=" + actual);
+    }
+  }
+
+  public static void main(String[] args) throws Exception {
+    Class<?> c = Class.forName("SsaBuilder");
+    Method m = c.getMethod("environmentPhi", new Class[] { boolean.class, int[].class });
+
+    int[] array = new int[3];
+    int result;
+
+    result = (Integer) m.invoke(null, new Object[] { true, array } );
+    assertEquals(2, result);
+
+    result = (Integer) m.invoke(null, new Object[] { false, array } );
+    assertEquals(0, result);
+  }
+}