Revert "Refactor HGraphBuilder and SsaBuilder to remove HLocals"

Bug: 27995065
This reverts commit e3ff7b293be2a6791fe9d135d660c0cffe4bd73f.

Change-Id: I5363c7ce18f47fd422c15eed5423a345a57249d8

1 files changed, 381 insertions, 50 deletions

diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index eeadbeb0d1..5a05256628 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -23,9 +23,30 @@
 
 namespace art {
 
+void SsaBuilder::SetLoopHeaderPhiInputs() {
+  for (size_t i = loop_headers_.size(); i > 0; --i) {
+    HBasicBlock* block = loop_headers_[i - 1];
+    for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
+      HPhi* phi = it.Current()->AsPhi();
+      size_t vreg = phi->GetRegNumber();
+      for (HBasicBlock* predecessor : block->GetPredecessors()) {
+        HInstruction* value = ValueOfLocal(predecessor, vreg);
+        if (value == nullptr) {
+          // Vreg is undefined at this predecessor. Mark it dead and leave with
+          // fewer inputs than predecessors. SsaChecker will fail if not removed.
+          phi->SetDead();
+          break;
+        } else {
+          phi->AddInput(value);
+        }
+      }
+    }
+  }
+}
+
 void SsaBuilder::FixNullConstantType() {
   // The order doesn't matter here.
-  for (HReversePostOrderIterator itb(*graph_); !itb.Done(); itb.Advance()) {
+  for (HReversePostOrderIterator itb(*GetGraph()); !itb.Done(); itb.Advance()) {
     for (HInstructionIterator it(itb.Current()->GetInstructions()); !it.Done(); it.Advance()) {
       HInstruction* equality_instr = it.Current();
       if (!equality_instr->IsEqual() && !equality_instr->IsNotEqual()) {
@@ -50,14 +71,14 @@ void SsaBuilder::FixNullConstantType() {
       // can only be the 0 constant.
       DCHECK(int_operand->IsIntConstant()) << int_operand->DebugName();
       DCHECK_EQ(0, int_operand->AsIntConstant()->GetValue());
-      equality_instr->ReplaceInput(graph_->GetNullConstant(), int_operand == right ? 1 : 0);
+      equality_instr->ReplaceInput(GetGraph()->GetNullConstant(), int_operand == right ? 1 : 0);
     }
   }
 }
 
 void SsaBuilder::EquivalentPhisCleanup() {
   // The order doesn't matter here.
-  for (HReversePostOrderIterator itb(*graph_); !itb.Done(); itb.Advance()) {
+  for (HReversePostOrderIterator itb(*GetGraph()); !itb.Done(); itb.Advance()) {
     for (HInstructionIterator it(itb.Current()->GetPhis()); !it.Done(); it.Advance()) {
       HPhi* phi = it.Current()->AsPhi();
       HPhi* next = phi->GetNextEquivalentPhiWithSameType();
@@ -79,7 +100,7 @@ void SsaBuilder::EquivalentPhisCleanup() {
 }
 
 void SsaBuilder::FixEnvironmentPhis() {
-  for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
+  for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) {
     HBasicBlock* block = it.Current();
     for (HInstructionIterator it_phis(block->GetPhis()); !it_phis.Done(); it_phis.Advance()) {
       HPhi* phi = it_phis.Current()->AsPhi();
@@ -233,9 +254,9 @@ bool SsaBuilder::UpdatePrimitiveType(HPhi* phi, ArenaVector<HPhi*>* worklist) {
 }
 
 void SsaBuilder::RunPrimitiveTypePropagation() {
-  ArenaVector<HPhi*> worklist(graph_->GetArena()->Adapter());
+  ArenaVector<HPhi*> worklist(GetGraph()->GetArena()->Adapter());
 
-  for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
+  for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) {
     HBasicBlock* block = it.Current();
     if (block->IsLoopHeader()) {
       for (HInstructionIterator phi_it(block->GetPhis()); !phi_it.Done(); phi_it.Advance()) {
@@ -279,14 +300,8 @@ void SsaBuilder::ProcessPrimitiveTypePropagationWorklist(ArenaVector<HPhi*>* wor
 static HArrayGet* FindFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget) {
   Primitive::Type type = aget->GetType();
   DCHECK(Primitive::IsIntOrLongType(type));
-  HInstruction* next = aget->GetNext();
-  if (next != nullptr && next->IsArrayGet()) {
-    HArrayGet* next_aget = next->AsArrayGet();
-    if (next_aget->IsEquivalentOf(aget)) {
-      return next_aget;
-    }
-  }
-  return nullptr;
+  HArrayGet* next = aget->GetNext()->AsArrayGet();
+  return (next != nullptr && next->IsEquivalentOf(aget)) ? next : nullptr;
 }
 
 static HArrayGet* CreateFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget) {
@@ -319,7 +334,7 @@ bool SsaBuilder::FixAmbiguousArrayOps() {
   // uses (because they are untyped) and environment uses (if --debuggable).
   // After resolving all ambiguous ArrayGets, we will re-run primitive type
   // propagation on the Phis which need to be updated.
-  ArenaVector<HPhi*> worklist(graph_->GetArena()->Adapter());
+  ArenaVector<HPhi*> worklist(GetGraph()->GetArena()->Adapter());
 
   {
     ScopedObjectAccess soa(Thread::Current());
@@ -437,7 +452,7 @@ static bool HasAliasInEnvironments(HInstruction* instruction) {
 }
 
 void SsaBuilder::RemoveRedundantUninitializedStrings() {
-  if (graph_->IsDebuggable()) {
+  if (GetGraph()->IsDebuggable()) {
     // Do not perform the optimization for consistency with the interpreter
     // which always allocates an object for new-instance of String.
     return;
@@ -445,13 +460,11 @@ void SsaBuilder::RemoveRedundantUninitializedStrings() {
 
   for (HNewInstance* new_instance : uninitialized_strings_) {
     DCHECK(new_instance->IsInBlock());
-    DCHECK(new_instance->IsStringAlloc());
-
     // Replace NewInstance of String with NullConstant if not used prior to
     // calling StringFactory. In case of deoptimization, the interpreter is
     // expected to skip null check on the `this` argument of the StringFactory call.
     if (!new_instance->HasNonEnvironmentUses() && !HasAliasInEnvironments(new_instance)) {
-      new_instance->ReplaceWith(graph_->GetNullConstant());
+      new_instance->ReplaceWith(GetGraph()->GetNullConstant());
       new_instance->GetBlock()->RemoveInstruction(new_instance);
 
       // Remove LoadClass if not needed any more.
@@ -482,47 +495,57 @@ void SsaBuilder::RemoveRedundantUninitializedStrings() {
 }
 
 GraphAnalysisResult SsaBuilder::BuildSsa() {
-  DCHECK(!graph_->IsInSsaForm());
+  DCHECK(!GetGraph()->IsInSsaForm());
 
-  // 1) Propagate types of phis. At this point, phis are typed void in the general
+  // 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 header phis.
+  SetLoopHeaderPhiInputs();
+
+  // 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.
   RunPrimitiveTypePropagation();
 
-  // 2) Now that the correct primitive types have been assigned, we can get rid
+  // 4) Now that the correct primitive types have been assigned, 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(graph_).Run();
+  SsaRedundantPhiElimination(GetGraph()).Run();
 
-  // 3) Fix the type for null constants which are part of an equality comparison.
+  // 5) 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();
 
-  // 4) Compute type of reference type instructions. The pass assumes that
+  // 6) Compute type of reference type instructions. The pass assumes that
   // NullConstant has been fixed up.
-  ReferenceTypePropagation(graph_, handles_, /* is_first_run */ true).Run();
+  ReferenceTypePropagation(GetGraph(), handles_, /* is_first_run */ true).Run();
 
-  // 5) HInstructionBuilder duplicated ArrayGet instructions with ambiguous type
-  // (int/float or long/double) and marked ArraySets with ambiguous input type.
-  // Now that RTP computed the type of the array input, the ambiguity can be
-  // resolved and the correct equivalents kept.
+  // 7) Step 1) duplicated ArrayGet instructions with ambiguous type (int/float
+  // or long/double) and marked ArraySets with ambiguous input type. Now that RTP
+  // computed the type of the array input, the ambiguity can be resolved and the
+  // correct equivalents kept.
   if (!FixAmbiguousArrayOps()) {
     return kAnalysisFailAmbiguousArrayOp;
   }
 
-  // 6) Mark dead phis. This will mark phis which are not used by instructions
+  // 8) 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_phi_elimimation(graph_);
+  SsaDeadPhiElimination dead_phi_elimimation(GetGraph());
   dead_phi_elimimation.MarkDeadPhis();
 
-  // 7) Make sure environments use the right phi equivalent: a phi marked dead
+  // 9) 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
@@ -531,26 +554,165 @@ GraphAnalysisResult SsaBuilder::BuildSsa() {
   // environments to just reference one.
   FixEnvironmentPhis();
 
-  // 8) Now that the right phis are used for the environments, we can eliminate
+  // 10) 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_phi_elimimation.EliminateDeadPhis();
 
-  // 9) HInstructionBuidler replaced uses of NewInstances of String with the
-  // results of their corresponding StringFactory calls. Unless the String
-  // objects are used before they are initialized, they can be replaced with
-  // NullConstant. Note that this optimization is valid only if unsimplified
-  // code does not use the uninitialized value because we assume execution can
-  // be deoptimized at any safepoint. We must therefore perform it before any
-  // other optimizations.
+  // 11) Step 1) replaced uses of NewInstances of String with the results of
+  // their corresponding StringFactory calls. Unless the String objects are used
+  // before they are initialized, they can be replaced with NullConstant.
+  // Note that this optimization is valid only if unsimplified code does not use
+  // the uninitialized value because we assume execution can be deoptimized at
+  // any safepoint. We must therefore perform it before any other optimizations.
   RemoveRedundantUninitializedStrings();
 
-  graph_->SetInSsaForm();
+  // 12) Clear locals.
+  for (HInstructionIterator it(GetGraph()->GetEntryBlock()->GetInstructions());
+       !it.Done();
+       it.Advance()) {
+    HInstruction* current = it.Current();
+    if (current->IsLocal()) {
+      current->GetBlock()->RemoveInstruction(current);
+    }
+  }
+
+  GetGraph()->SetInSsaForm();
   return kAnalysisSuccess;
 }
 
+ArenaVector<HInstruction*>* SsaBuilder::GetLocalsFor(HBasicBlock* block) {
+  ArenaVector<HInstruction*>* locals = &locals_for_[block->GetBlockId()];
+  const size_t vregs = GetGraph()->GetNumberOfVRegs();
+  if (locals->empty() && vregs != 0u) {
+    locals->resize(vregs, nullptr);
+
+    if (block->IsCatchBlock()) {
+      ArenaAllocator* arena = GetGraph()->GetArena();
+      // We record incoming inputs of catch phis at throwing instructions and
+      // must therefore eagerly create the phis. Phis for undefined vregs will
+      // be deleted when the first throwing instruction with the vreg undefined
+      // is encountered. Unused phis will be removed by dead phi analysis.
+      for (size_t i = 0; i < vregs; ++i) {
+        // No point in creating the catch phi if it is already undefined at
+        // the first throwing instruction.
+        HInstruction* current_local_value = (*current_locals_)[i];
+        if (current_local_value != nullptr) {
+          HPhi* phi = new (arena) HPhi(
+              arena,
+              i,
+              0,
+              current_local_value->GetType());
+          block->AddPhi(phi);
+          (*locals)[i] = phi;
+        }
+      }
+    }
+  }
+  return locals;
+}
+
+HInstruction* SsaBuilder::ValueOfLocal(HBasicBlock* block, size_t local) {
+  ArenaVector<HInstruction*>* locals = GetLocalsFor(block);
+  return (*locals)[local];
+}
+
+void SsaBuilder::VisitBasicBlock(HBasicBlock* block) {
+  current_locals_ = GetLocalsFor(block);
+
+  if (block->IsCatchBlock()) {
+    // Catch phis were already created and inputs collected from throwing sites.
+    if (kIsDebugBuild) {
+      // Make sure there was at least one throwing instruction which initialized
+      // locals (guaranteed by HGraphBuilder) and that all try blocks have been
+      // visited already (from HTryBoundary scoping and reverse post order).
+      bool catch_block_visited = false;
+      for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) {
+        HBasicBlock* current = it.Current();
+        if (current == block) {
+          catch_block_visited = true;
+        } else if (current->IsTryBlock() &&
+                   current->GetTryCatchInformation()->GetTryEntry().HasExceptionHandler(*block)) {
+          DCHECK(!catch_block_visited) << "Catch block visited before its try block.";
+        }
+      }
+      DCHECK_EQ(current_locals_->size(), GetGraph()->GetNumberOfVRegs())
+          << "No instructions throwing into a live catch block.";
+    }
+  } else if (block->IsLoopHeader()) {
+    // If the block is a loop header, we know we only have visited the pre header
+    // because we are visiting in reverse post order. We create phis for all initialized
+    // locals from the pre header. Their inputs will be populated at the end of
+    // the analysis.
+    for (size_t local = 0; local < current_locals_->size(); ++local) {
+      HInstruction* incoming = ValueOfLocal(block->GetLoopInformation()->GetPreHeader(), local);
+      if (incoming != nullptr) {
+        HPhi* phi = new (GetGraph()->GetArena()) HPhi(
+            GetGraph()->GetArena(),
+            local,
+            0,
+            incoming->GetType());
+        block->AddPhi(phi);
+        (*current_locals_)[local] = phi;
+      }
+    }
+    // Save the loop header so that the last phase of the analysis knows which
+    // blocks need to be updated.
+    loop_headers_.push_back(block);
+  } else if (block->GetPredecessors().size() > 0) {
+    // All predecessors have already been visited because we are visiting in reverse post order.
+    // We merge the values of all locals, creating phis if those values differ.
+    for (size_t local = 0; local < current_locals_->size(); ++local) {
+      bool one_predecessor_has_no_value = false;
+      bool is_different = false;
+      HInstruction* value = ValueOfLocal(block->GetPredecessors()[0], local);
+
+      for (HBasicBlock* predecessor : block->GetPredecessors()) {
+        HInstruction* current = ValueOfLocal(predecessor, local);
+        if (current == nullptr) {
+          one_predecessor_has_no_value = true;
+          break;
+        } else if (current != value) {
+          is_different = true;
+        }
+      }
+
+      if (one_predecessor_has_no_value) {
+        // If one predecessor has no value for this local, we trust the verifier has
+        // successfully checked that there is a store dominating any read after this block.
+        continue;
+      }
+
+      if (is_different) {
+        HInstruction* first_input = ValueOfLocal(block->GetPredecessors()[0], local);
+        HPhi* phi = new (GetGraph()->GetArena()) HPhi(
+            GetGraph()->GetArena(),
+            local,
+            block->GetPredecessors().size(),
+            first_input->GetType());
+        for (size_t i = 0; i < block->GetPredecessors().size(); i++) {
+          HInstruction* pred_value = ValueOfLocal(block->GetPredecessors()[i], local);
+          phi->SetRawInputAt(i, pred_value);
+        }
+        block->AddPhi(phi);
+        value = phi;
+      }
+      (*current_locals_)[local] = value;
+    }
+  }
+
+  // Visit all instructions. The instructions of interest are:
+  // - HLoadLocal: replace them with the current value of the local.
+  // - HStoreLocal: update current value of the local and remove the instruction.
+  // - Instructions that require an environment: populate their environment
+  //   with the current values of the locals.
+  for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
+    it.Current()->Accept(this);
+  }
+}
+
 /**
  * Constants in the Dex format are not typed. So the builder types them as
  * integers, but when doing the SSA form, we might realize the constant
@@ -561,10 +723,11 @@ HFloatConstant* SsaBuilder::GetFloatEquivalent(HIntConstant* constant) {
   // We place the floating point constant next to this constant.
   HFloatConstant* result = constant->GetNext()->AsFloatConstant();
   if (result == nullptr) {
-    float value = bit_cast<float, int32_t>(constant->GetValue());
-    result = new (graph_->GetArena()) HFloatConstant(value);
+    HGraph* graph = constant->GetBlock()->GetGraph();
+    ArenaAllocator* allocator = graph->GetArena();
+    result = new (allocator) HFloatConstant(bit_cast<float, int32_t>(constant->GetValue()));
     constant->GetBlock()->InsertInstructionBefore(result, constant->GetNext());
-    graph_->CacheFloatConstant(result);
+    graph->CacheFloatConstant(result);
   } else {
     // If there is already a constant with the expected type, we know it is
     // the floating point equivalent of this constant.
@@ -583,10 +746,11 @@ HDoubleConstant* SsaBuilder::GetDoubleEquivalent(HLongConstant* constant) {
   // We place the floating point constant next to this constant.
   HDoubleConstant* result = constant->GetNext()->AsDoubleConstant();
   if (result == nullptr) {
-    double value = bit_cast<double, int64_t>(constant->GetValue());
-    result = new (graph_->GetArena()) HDoubleConstant(value);
+    HGraph* graph = constant->GetBlock()->GetGraph();
+    ArenaAllocator* allocator = graph->GetArena();
+    result = new (allocator) HDoubleConstant(bit_cast<double, int64_t>(constant->GetValue()));
     constant->GetBlock()->InsertInstructionBefore(result, constant->GetNext());
-    graph_->CacheDoubleConstant(result);
+    graph->CacheDoubleConstant(result);
   } else {
     // If there is already a constant with the expected type, we know it is
     // the floating point equivalent of this constant.
@@ -617,7 +781,7 @@ HPhi* SsaBuilder::GetFloatDoubleOrReferenceEquivalentOfPhi(HPhi* phi, Primitive:
   if (next == nullptr
       || (next->AsPhi()->GetRegNumber() != phi->GetRegNumber())
       || (next->GetType() != type)) {
-    ArenaAllocator* allocator = graph_->GetArena();
+    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
@@ -677,7 +841,7 @@ HInstruction* SsaBuilder::GetFloatOrDoubleEquivalent(HInstruction* value, Primit
 
 HInstruction* SsaBuilder::GetReferenceTypeEquivalent(HInstruction* value) {
   if (value->IsIntConstant() && value->AsIntConstant()->GetValue() == 0) {
-    return graph_->GetNullConstant();
+    return value->GetBlock()->GetGraph()->GetNullConstant();
   } else if (value->IsPhi()) {
     return GetFloatDoubleOrReferenceEquivalentOfPhi(value->AsPhi(), Primitive::kPrimNot);
   } else {
@@ -685,4 +849,171 @@ HInstruction* SsaBuilder::GetReferenceTypeEquivalent(HInstruction* value) {
   }
 }
 
+void SsaBuilder::VisitLoadLocal(HLoadLocal* load) {
+  Primitive::Type load_type = load->GetType();
+  HInstruction* value = (*current_locals_)[load->GetLocal()->GetRegNumber()];
+  // If the operation requests a specific type, we make sure its input is of that type.
+  if (load_type != value->GetType()) {
+    if (load_type == Primitive::kPrimFloat || load_type == Primitive::kPrimDouble) {
+      value = GetFloatOrDoubleEquivalent(value, load_type);
+    } else if (load_type == Primitive::kPrimNot) {
+      value = GetReferenceTypeEquivalent(value);
+    }
+  }
+
+  load->ReplaceWith(value);
+  load->GetBlock()->RemoveInstruction(load);
+}
+
+void SsaBuilder::VisitStoreLocal(HStoreLocal* store) {
+  uint32_t reg_number = store->GetLocal()->GetRegNumber();
+  HInstruction* stored_value = store->InputAt(1);
+  Primitive::Type stored_type = stored_value->GetType();
+  DCHECK_NE(stored_type, Primitive::kPrimVoid);
+
+  // Storing into vreg `reg_number` may implicitly invalidate the surrounding
+  // registers. Consider the following cases:
+  // (1) Storing a wide value must overwrite previous values in both `reg_number`
+  //     and `reg_number+1`. We store `nullptr` in `reg_number+1`.
+  // (2) If vreg `reg_number-1` holds a wide value, writing into `reg_number`
+  //     must invalidate it. We store `nullptr` in `reg_number-1`.
+  // Consequently, storing a wide value into the high vreg of another wide value
+  // will invalidate both `reg_number-1` and `reg_number+1`.
+
+  if (reg_number != 0) {
+    HInstruction* local_low = (*current_locals_)[reg_number - 1];
+    if (local_low != nullptr && Primitive::Is64BitType(local_low->GetType())) {
+      // The vreg we are storing into was previously the high vreg of a pair.
+      // We need to invalidate its low vreg.
+      DCHECK((*current_locals_)[reg_number] == nullptr);
+      (*current_locals_)[reg_number - 1] = nullptr;
+    }
+  }
+
+  (*current_locals_)[reg_number] = stored_value;
+  if (Primitive::Is64BitType(stored_type)) {
+    // We are storing a pair. Invalidate the instruction in the high vreg.
+    (*current_locals_)[reg_number + 1] = nullptr;
+  }
+
+  store->GetBlock()->RemoveInstruction(store);
+}
+
+bool SsaBuilder::IsFirstAtThrowingDexPc(HInstruction* instruction) const {
+  uint32_t dex_pc = instruction->GetDexPc();
+  if (dex_pc == kNoDexPc) {
+    return false;
+  }
+
+  // Needs to be the first HInstruction with this dex_pc.
+  HInstruction* previous = instruction->GetPrevious();
+  if (previous != nullptr && previous->GetDexPc() == dex_pc) {
+    return false;
+  }
+
+  if (instruction->IsControlFlow() && !instruction->IsThrow()) {
+    // Special-case non-throwing control-flow HInstruction because artifically
+    // created ones are given dex_pc of the nearest bytecode instructions.
+    return false;
+  }
+
+  return IsThrowingDexInstruction(GetDexInstructionAt(code_item_, dex_pc));
+}
+
+void SsaBuilder::VisitInstruction(HInstruction* instruction) {
+  if (instruction->NeedsEnvironment()) {
+    HEnvironment* environment = new (GetGraph()->GetArena()) HEnvironment(
+        GetGraph()->GetArena(),
+        current_locals_->size(),
+        GetGraph()->GetDexFile(),
+        GetGraph()->GetMethodIdx(),
+        instruction->GetDexPc(),
+        GetGraph()->GetInvokeType(),
+        instruction);
+    environment->CopyFrom(*current_locals_);
+    instruction->SetRawEnvironment(environment);
+  }
+
+  // If in a try block, propagate values of locals into catch blocks.
+  if (instruction->GetBlock()->IsTryBlock() && IsFirstAtThrowingDexPc(instruction)) {
+    const HTryBoundary& try_entry =
+        instruction->GetBlock()->GetTryCatchInformation()->GetTryEntry();
+    for (HBasicBlock* catch_block : try_entry.GetExceptionHandlers()) {
+      ArenaVector<HInstruction*>* handler_locals = GetLocalsFor(catch_block);
+      DCHECK_EQ(handler_locals->size(), current_locals_->size());
+      for (size_t vreg = 0, e = current_locals_->size(); vreg < e; ++vreg) {
+        HInstruction* handler_value = (*handler_locals)[vreg];
+        if (handler_value == nullptr) {
+          // Vreg was undefined at a previously encountered throwing instruction
+          // and the catch phi was deleted. Do not record the local value.
+          continue;
+        }
+        DCHECK(handler_value->IsPhi());
+
+        HInstruction* local_value = (*current_locals_)[vreg];
+        if (local_value == nullptr) {
+          // This is the first instruction throwing into `catch_block` where
+          // `vreg` is undefined. Delete the catch phi.
+          catch_block->RemovePhi(handler_value->AsPhi());
+          (*handler_locals)[vreg] = nullptr;
+        } else {
+          // Vreg has been defined at all instructions throwing into `catch_block`
+          // encountered so far. Record the local value in the catch phi.
+          handler_value->AsPhi()->AddInput(local_value);
+        }
+      }
+    }
+  }
+}
+
+void SsaBuilder::VisitArrayGet(HArrayGet* aget) {
+  Primitive::Type type = aget->GetType();
+  DCHECK(!Primitive::IsFloatingPointType(type));
+  if (Primitive::IsIntOrLongType(type)) {
+    ambiguous_agets_.push_back(aget);
+  }
+  VisitInstruction(aget);
+}
+
+void SsaBuilder::VisitArraySet(HArraySet* aset) {
+  Primitive::Type type = aset->GetValue()->GetType();
+  if (Primitive::IsIntOrLongType(type)) {
+    ambiguous_asets_.push_back(aset);
+  }
+  VisitInstruction(aset);
+}
+
+void SsaBuilder::VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) {
+  VisitInstruction(invoke);
+
+  if (invoke->IsStringInit()) {
+    // This is a StringFactory call which acts as a String constructor. Its
+    // result replaces the empty String pre-allocated by NewInstance.
+    HInstruction* arg_this = invoke->GetAndRemoveThisArgumentOfStringInit();
+
+    // Replacing the NewInstance might render it redundant. Keep a list of these
+    // to be visited once it is clear whether it is has remaining uses.
+    if (arg_this->IsNewInstance()) {
+      HNewInstance* new_instance = arg_this->AsNewInstance();
+      // Note that in some rare cases (b/27847265), the same NewInstance may be seen
+      // multiple times. We should only consider it once for removal, so we
+      // ensure it is not added more than once.
+      if (!ContainsElement(uninitialized_strings_, new_instance)) {
+        uninitialized_strings_.push_back(new_instance);
+      }
+    } else {
+      DCHECK(arg_this->IsPhi());
+      // NewInstance is not the direct input of the StringFactory call. It might
+      // be redundant but optimizing this case is not worth the effort.
+    }
+
+    // Walk over all vregs and replace any occurrence of `arg_this` with `invoke`.
+    for (size_t vreg = 0, e = current_locals_->size(); vreg < e; ++vreg) {
+      if ((*current_locals_)[vreg] == arg_this) {
+        (*current_locals_)[vreg] = invoke;
+      }
+    }
+  }
+}
+
 }  // namespace art