/*
 * 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.
 */

#include "ssa_builder.h"

#include "base/arena_bit_vector.h"
#include "base/bit_vector-inl.h"
#include "base/logging.h"
#include "data_type-inl.h"
#include "dex/bytecode_utils.h"
#include "mirror/class-inl.h"
#include "nodes.h"
#include "reference_type_propagation.h"
#include "scoped_thread_state_change-inl.h"
#include "ssa_phi_elimination.h"

namespace art HIDDEN {

void SsaBuilder::FixNullConstantType() {
  // The order doesn't matter here.
  for (HBasicBlock* block : graph_->GetReversePostOrder()) {
    for (HInstructionIteratorPrefetchNext it(block->GetInstructions()); !it.Done(); it.Advance()) {
      HInstruction* equality_instr = it.Current();
      if (!equality_instr->IsEqual() && !equality_instr->IsNotEqual()) {
        continue;
      }
      HInstruction* left = equality_instr->InputAt(0);
      HInstruction* right = equality_instr->InputAt(1);
      HInstruction* int_operand = nullptr;

      if ((left->GetType() == DataType::Type::kReference) &&
          (right->GetType() == DataType::Type::kInt32)) {
        int_operand = right;
      } else if ((right->GetType() == DataType::Type::kReference) &&
                 (left->GetType() == DataType::Type::kInt32)) {
        int_operand = left;
      } else {
        continue;
      }

      // If we got here, we are comparing against a reference and the int constant
      // should be replaced with a null constant.
      // Both type propagation and redundant phi elimination ensure `int_operand`
      // 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);
    }
  }
}

void SsaBuilder::EquivalentPhisCleanup() {
  // The order doesn't matter here.
  for (HBasicBlock* block : graph_->GetReversePostOrder()) {
    for (HInstructionIteratorPrefetchNext it(block->GetPhis()); !it.Done(); it.Advance()) {
      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.
        if (next->IsLive()) {
          phi->ReplaceWith(next);
          phi->SetDead();
        } else {
          next->ReplaceWith(phi);
        }
        DCHECK(next->GetNextEquivalentPhiWithSameType() == nullptr)
            << "More then one phi equivalent with type " << phi->GetType()
            << " found for phi" << phi->GetId();
      }
    }
  }
}

void SsaBuilder::FixEnvironmentPhis() {
  for (HBasicBlock* block : graph_->GetReversePostOrder()) {
    for (HInstructionIteratorPrefetchNext it_phis(block->GetPhis()); !it_phis.Done();
         it_phis.Advance()) {
      HPhi* phi = it_phis.Current()->AsPhi();
      // If the phi is not dead, or has no environment uses, there is nothing to do.
      if (!phi->IsDead() || !phi->HasEnvironmentUses()) continue;
      HInstruction* next = phi->GetNext();
      if (!phi->IsVRegEquivalentOf(next)) continue;
      if (next->AsPhi()->IsDead()) {
        // If the phi equivalent is dead, check if there is another one.
        next = next->GetNext();
        if (!phi->IsVRegEquivalentOf(next)) continue;
        // There can be at most two phi equivalents.
        DCHECK(!phi->IsVRegEquivalentOf(next->GetNext()));
        if (next->AsPhi()->IsDead()) continue;
      }
      // We found a live phi equivalent. Update the environment uses of `phi` with it.
      phi->ReplaceWith(next);
    }
  }
}

static void AddDependentInstructionsToWorklist(HInstruction* instruction,
                                               ScopedArenaVector<HPhi*>* worklist) {
  // 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 (const HUseListNode<HInstruction*>& use : instruction->GetUses()) {
    HInstruction* user = use.GetUser();
    if (user->IsPhi() && user->AsPhi()->IsLive()) {
      if (add_all_live_phis || user->GetType() != instruction->GetType()) {
        worklist->push_back(user->AsPhi());
      }
    }
  }
}

// Find a candidate primitive type for `phi` by merging the type of its inputs.
// Return false if conflict is identified.
static bool TypePhiFromInputs(HPhi* phi) {
  DataType::Type common_type = phi->GetType();

  for (HInstruction* input : phi->GetInputs()) {
    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;
    }

    DataType::Type input_type = HPhi::ToPhiType(input->GetType());
    if (common_type == input_type) {
      // No change in type.
    } else if (DataType::Is64BitType(common_type) != DataType::Is64BitType(input_type)) {
      // Types are of different sizes, e.g. int vs. long. Must be a conflict.
      return false;
    } else if (DataType::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(DataType::IsFloatingPointType(input_type) ||
             input_type == DataType::Type::kReference);
      common_type = input_type;
    } else if (DataType::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(DataType::IsFloatingPointType(common_type) ||
             common_type == DataType::Type::kReference);
    } else {
      // Combining float and reference types. Clearly a conflict.
      DCHECK(
          (common_type == DataType::Type::kFloat32 && input_type == DataType::Type::kReference) ||
          (common_type == DataType::Type::kReference && input_type == DataType::Type::kFloat32));
      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;
}

// Replace inputs of `phi` to match its type. Return false if conflict is identified.
bool SsaBuilder::TypeInputsOfPhi(HPhi* phi, ScopedArenaVector<HPhi*>* worklist) {
  DataType::Type common_type = phi->GetType();
  if (DataType::IsIntegralType(common_type)) {
    // We do not need to retype ambiguous inputs because they are always constructed
    // with the integral type candidate.
    if (kIsDebugBuild) {
      for (HInstruction* input : phi->GetInputs()) {
        DCHECK(HPhi::ToPhiType(input->GetType()) == common_type);
      }
    }
    // Inputs did not need to be replaced, hence no conflict. Report success.
    return true;
  } else {
    DCHECK(common_type == DataType::Type::kReference ||
           DataType::IsFloatingPointType(common_type));
    HInputsRef inputs = phi->GetInputs();
    for (size_t i = 0; i < inputs.size(); ++i) {
      HInstruction* input = inputs[i];
      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 == DataType::Type::kReference)
            ? GetReferenceTypeEquivalent(input)
            : GetFloatOrDoubleEquivalent(input, common_type);
        if (equivalent == nullptr) {
          // Input could not be typed. Report conflict.
          return false;
        }
        // Make sure the input did not change its type and we do not need to
        // update its users.
        DCHECK_NE(input, equivalent);

        phi->ReplaceInput(equivalent, i);
        if (equivalent->IsPhi()) {
          worklist->push_back(equivalent->AsPhi());
        }
      }
    }
    // All inputs either matched the type of the phi or we successfully replaced
    // them with a suitable equivalent. Report success.
    return true;
  }
}

// Attempt to set the primitive type of `phi` to match its inputs. Return whether
// it was changed by the algorithm or not.
bool SsaBuilder::UpdatePrimitiveType(HPhi* phi, ScopedArenaVector<HPhi*>* worklist) {
  DCHECK(phi->IsLive());
  DataType::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, worklist)) {
    // Conflict detected. Mark the phi dead and return true because it changed.
    phi->SetDead();
    return true;
  }

  // Return true if the type of the phi has changed.
  return phi->GetType() != original_type;
}

void SsaBuilder::RunPrimitiveTypePropagation() {
  ScopedArenaVector<HPhi*> worklist(local_allocator_->Adapter(kArenaAllocGraphBuilder));

  for (HBasicBlock* block : graph_->GetReversePostOrder()) {
    if (block->IsLoopHeader()) {
      for (HInstructionIteratorPrefetchNext phi_it(block->GetPhis()); !phi_it.Done();
           phi_it.Advance()) {
        HPhi* phi = phi_it.Current()->AsPhi();
        if (phi->IsLive()) {
          worklist.push_back(phi);
        }
      }
    } else {
      for (HInstructionIteratorPrefetchNext phi_it(block->GetPhis()); !phi_it.Done();
           phi_it.Advance()) {
        // Eagerly compute the type of the phi, for quicker convergence. Note
        // that we don't need to add users to the worklist because we are
        // doing a reverse post-order visit, therefore either the phi users are
        // non-loop phi and will be visited later in the visit, or are loop-phis,
        // and they are already in the work list.
        HPhi* phi = phi_it.Current()->AsPhi();
        if (phi->IsLive()) {
          UpdatePrimitiveType(phi, &worklist);
        }
      }
    }
  }

  ProcessPrimitiveTypePropagationWorklist(&worklist);
  EquivalentPhisCleanup();
}

void SsaBuilder::ProcessPrimitiveTypePropagationWorklist(ScopedArenaVector<HPhi*>* worklist) {
  // Process worklist
  while (!worklist->empty()) {
    HPhi* phi = worklist->back();
    worklist->pop_back();
    // 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() && UpdatePrimitiveType(phi, worklist)) {
      AddDependentInstructionsToWorklist(phi, worklist);
    }
  }
}

static HArrayGet* FindFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget) {
  DataType::Type type = aget->GetType();
  DCHECK(DataType::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;
}

static HArrayGet* CreateFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget) {
  DataType::Type type = aget->GetType();
  DCHECK(DataType::IsIntOrLongType(type));
  DCHECK(FindFloatOrDoubleEquivalentOfArrayGet(aget) == nullptr);

  HArrayGet* equivalent = new (aget->GetBlock()->GetGraph()->GetAllocator()) HArrayGet(
      aget->GetArray(),
      aget->GetIndex(),
      type == DataType::Type::kInt32 ? DataType::Type::kFloat32 : DataType::Type::kFloat64,
      aget->GetDexPc());
  aget->GetBlock()->InsertInstructionAfter(equivalent, aget);
  return equivalent;
}

static DataType::Type GetPrimitiveArrayComponentType(HInstruction* array)
    REQUIRES_SHARED(Locks::mutator_lock_) {
  ReferenceTypeInfo array_type = array->GetReferenceTypeInfo();
  DCHECK(array_type.IsPrimitiveArrayClass());
  return DataTypeFromPrimitive(
      array_type.GetTypeHandle()->GetComponentType()->GetPrimitiveType());
}

bool SsaBuilder::FixAmbiguousArrayOps() {
  if (ambiguous_agets_.empty() && ambiguous_asets_.empty()) {
    return true;
  }

  // The wrong ArrayGet equivalent may still have Phi uses coming from ArraySet
  // 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.
  ScopedArenaVector<HPhi*> worklist(local_allocator_->Adapter(kArenaAllocGraphBuilder));

  {
    ScopedObjectAccess soa(Thread::Current());

    for (HArrayGet* aget_int : ambiguous_agets_) {
      HInstruction* array = aget_int->GetArray();
      if (!array->GetReferenceTypeInfo().IsValid() ||
          !array->GetReferenceTypeInfo().IsPrimitiveArrayClass()) {
        // RTP did not type the input array. Bail.
        VLOG(compiler) << "Not compiled: Could not infer an array type for array operation at "
                       << aget_int->GetDexPc();
        return false;
      }

      HArrayGet* aget_float = FindFloatOrDoubleEquivalentOfArrayGet(aget_int);
      DataType::Type array_type = GetPrimitiveArrayComponentType(array);
      DCHECK_EQ(DataType::Is64BitType(aget_int->GetType()), DataType::Is64BitType(array_type));

      if (DataType::IsIntOrLongType(array_type)) {
        if (aget_float != nullptr) {
          // There is a float/double equivalent. We must replace it and re-run
          // primitive type propagation on all dependent instructions.
          aget_float->ReplaceWith(aget_int);
          aget_float->GetBlock()->RemoveInstruction(aget_float);
          AddDependentInstructionsToWorklist(aget_int, &worklist);
        }
      } else {
        DCHECK(DataType::IsFloatingPointType(array_type));
        if (aget_float == nullptr) {
          // This is a float/double ArrayGet but there were no typed uses which
          // would create the typed equivalent. Create it now.
          aget_float = CreateFloatOrDoubleEquivalentOfArrayGet(aget_int);
        }
        // Replace the original int/long instruction. Note that it may have phi
        // uses, environment uses, as well as real uses (from untyped ArraySets).
        // We need to re-run primitive type propagation on its dependent instructions.
        aget_int->ReplaceWith(aget_float);
        aget_int->GetBlock()->RemoveInstruction(aget_int);
        AddDependentInstructionsToWorklist(aget_float, &worklist);
      }
    }

    // Set a flag stating that types of ArrayGets have been resolved. Requesting
    // equivalent of the wrong type with GetFloatOrDoubleEquivalentOfArrayGet
    // will fail from now on.
    agets_fixed_ = true;

    for (HArraySet* aset : ambiguous_asets_) {
      HInstruction* array = aset->GetArray();
      if (!array->GetReferenceTypeInfo().IsValid() ||
          !array->GetReferenceTypeInfo().IsPrimitiveArrayClass()) {
        // RTP did not type the input array. Bail.
        VLOG(compiler) << "Not compiled: Could not infer an array type for array operation at "
                       << aset->GetDexPc();
        return false;
      }

      HInstruction* value = aset->GetValue();
      DataType::Type value_type = value->GetType();
      DataType::Type array_type = GetPrimitiveArrayComponentType(array);
      DCHECK_EQ(DataType::Is64BitType(value_type), DataType::Is64BitType(array_type));

      if (DataType::IsFloatingPointType(array_type)) {
        if (!DataType::IsFloatingPointType(value_type)) {
          DCHECK(DataType::IsIntegralType(value_type));
          // Array elements are floating-point but the value has not been replaced
          // with its floating-point equivalent. The replacement must always
          // succeed in code validated by the verifier.
          HInstruction* equivalent = GetFloatOrDoubleEquivalent(value, array_type);
          DCHECK(equivalent != nullptr);
          aset->ReplaceInput(equivalent, /* index= */ 2);
          if (equivalent->IsPhi()) {
            // Returned equivalent is a phi which may not have had its inputs
            // replaced yet. We need to run primitive type propagation on it.
            worklist.push_back(equivalent->AsPhi());
          }
        }
        // Refine the side effects of this floating point aset. Note that we do this even if
        // no replacement occurs, since the right-hand-side may have been corrected already.
        aset->SetSideEffects(HArraySet::ComputeSideEffects(aset->GetComponentType()));
      } else {
        // Array elements are integral and the value assigned to it initially
        // was integral too. Nothing to do.
        DCHECK(DataType::IsIntegralType(array_type));
        DCHECK(DataType::IsIntegralType(value_type));
      }
    }
  }

  if (!worklist.empty()) {
    ProcessPrimitiveTypePropagationWorklist(&worklist);
    EquivalentPhisCleanup();
  }

  return true;
}

bool SsaBuilder::HasAliasInEnvironments(HInstruction* instruction) {
  ScopedArenaHashSet<size_t> seen_users(
      local_allocator_->Adapter(kArenaAllocGraphBuilder));
  for (const HUseListNode<HEnvironment*>& use : instruction->GetEnvUses()) {
    DCHECK(use.GetUser() != nullptr);
    size_t id = use.GetUser()->GetHolder()->GetId();
    if (seen_users.find(id) != seen_users.end()) {
      return true;
    }
    seen_users.insert(id);
  }
  return false;
}

bool SsaBuilder::ReplaceUninitializedStringPhis() {
  for (HInvoke* invoke : uninitialized_string_phis_) {
    HInstruction* str = invoke->InputAt(invoke->InputCount() - 1);
    if (str->IsPhi()) {
      // If after redundant phi and dead phi elimination, it's still a phi that feeds
      // the invoke, then we must be compiling a method with irreducible loops. Just bail.
      DCHECK(graph_->HasIrreducibleLoops());
      return false;
    }
    DCHECK(str->IsNewInstance());
    AddUninitializedString(str->AsNewInstance());
    str->ReplaceUsesDominatedBy(invoke, invoke);
    str->ReplaceEnvUsesDominatedBy(invoke, invoke);
    invoke->RemoveInputAt(invoke->InputCount() - 1);
  }
  return true;
}

void SsaBuilder::RemoveRedundantUninitializedStrings() {
  if (graph_->IsDebuggable()) {
    // Do not perform the optimization for consistency with the interpreter
    // which always allocates an object for new-instance of String.
    return;
  }

  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. We check for alias environments 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->GetBlock()->RemoveInstruction(new_instance);

      // Remove LoadClass if not needed any more.
      HInstruction* input = new_instance->InputAt(0);
      HLoadClass* load_class = nullptr;

      // If the class was not present in the dex cache at the point of building
      // the graph, the builder inserted a HClinitCheck in between. Since the String
      // class is always initialized at the point of running Java code, we can remove
      // that check.
      if (input->IsClinitCheck()) {
        load_class = input->InputAt(0)->AsLoadClass();
        input->ReplaceWith(load_class);
        input->GetBlock()->RemoveInstruction(input);
      } else {
        load_class = input->AsLoadClass();
        DCHECK(new_instance->IsStringAlloc());
        DCHECK(!load_class->NeedsAccessCheck()) << "String class is always accessible";
      }
      DCHECK(load_class != nullptr);
      if (!load_class->HasUses()) {
        // Even if the HLoadClass needs access check, we can remove it, as we know the
        // String class does not need it.
        load_class->GetBlock()->RemoveInstruction(load_class);
      }
    }
  }
}

static bool HasPhiEquivalentAtLoopEntry(HGraph* graph) {
  // Phi equivalents for a dex register do not work with OSR, as the phis will
  // receive two different stack slots but only one is recorded in the stack
  // map.
  for (HBasicBlock* block : graph->GetReversePostOrder()) {
    if (block->IsLoopHeader()) {
      for (HInstructionIteratorPrefetchNext it(block->GetPhis()); !it.Done(); it.Advance()) {
        if (it.Current()->AsPhi()->HasEquivalentPhi()) {
          return true;
        }
      }
    }
  }
  return false;
}

static bool IsSameSizeConstant(const HInstruction* insn1, const HInstruction* insn2) {
  return insn1->IsConstant()
      && insn2->IsConstant()
      && DataType::Is64BitType(insn1->GetType()) == DataType::Is64BitType(insn2->GetType());
}

static bool IsConstantEquivalent(const HInstruction* insn1,
                                 const HInstruction* insn2,
                                 BitVector* visited) {
  if (insn1->IsPhi() && insn1->AsPhi()->IsVRegEquivalentOf(insn2)) {
    HConstInputsRef insn1_inputs = insn1->GetInputs();
    HConstInputsRef insn2_inputs = insn2->GetInputs();
    if (insn1_inputs.size() != insn2_inputs.size()) {
      return false;
    }

    // Testing only one of the two inputs for recursion is sufficient.
    if (visited->IsBitSet(insn1->GetId())) {
      return true;
    }
    visited->SetBit(insn1->GetId());

    for (size_t i = 0; i < insn1_inputs.size(); ++i) {
      if (!IsConstantEquivalent(insn1_inputs[i], insn2_inputs[i], visited)) {
        return false;
      }
    }
    return true;
  } else if (IsSameSizeConstant(insn1, insn2)) {
    return insn1->AsConstant()->GetValueAsUint64() == insn2->AsConstant()->GetValueAsUint64();
  } else {
    return false;
  }
}

static void VerifyDuplicatePhis(HGraph* graph) {
  for (HBasicBlock* block : graph->GetReversePostOrderSkipEntryBlock()) {
    for (HInstructionIteratorPrefetchNext it(block->GetPhis()); !it.Done(); it.Advance()) {
      HPhi* phi = it.Current()->AsPhi();
      if (phi->GetRegNumber() == kNoRegNumber) {
        continue;
      }

      for (HInstructionIteratorPrefetchNext other_it(block->GetPhis()); !other_it.Done();
           other_it.Advance()) {
        HPhi* other_phi = other_it.Current()->AsPhi();
        if (phi == other_phi ||
            phi->GetRegNumber() != other_phi->GetRegNumber() ||
            phi->GetType() == other_phi->GetType() ||
            phi->GetType() == DataType::Type::kReference) {
          continue;
        }
        // Use local allocator for allocating memory.
        ScopedArenaAllocator allocator(graph->GetArenaStack());
        // If we get here, make sure we allocate all the necessary storage at once
        // because the BitVector reallocation strategy has very bad worst-case behavior.
        ArenaBitVector visited(&allocator,
                               graph->GetCurrentInstructionId(),
                               /* expandable= */ false,
                               kArenaAllocGraphChecker);
        if (!IsConstantEquivalent(phi, other_phi, &visited)) {
          LOG(FATAL) << "Two phis (" << phi->GetId() << " and " << other_phi->GetId()
                     << ") found for VReg " << phi->GetRegNumber()
                     << " but they are not equivalents of constants.";
          UNREACHABLE();
        }
      }
    }
  }
  return;
}

GraphAnalysisResult SsaBuilder::BuildSsa() {
  DCHECK(!graph_->IsInSsaForm());

  // 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();

  // 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();

  // 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();

  // Compute type of reference type instructions. The pass assumes that
  // NullConstant has been fixed up.
  ReferenceTypePropagation(graph_,
                           dex_cache_,
                           /* is_first_run= */ true).Run();

  // 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.
  if (!FixAmbiguousArrayOps()) {
    return kAnalysisFailAmbiguousArrayOp;
  }

  // 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_);
  dead_phi_elimimation.MarkDeadPhis();

  // 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();

  // 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();

  // Replace Phis that feed in a String.<init> during instruction building. We
  // run this after redundant and dead phi elimination to make sure the phi will have
  // been replaced by the actual allocation. Only with an irreducible loop
  // a phi can still be the input, in which case we bail.
  if (!ReplaceUninitializedStringPhis()) {
    return kAnalysisFailIrreducibleLoopAndStringInit;
  }

  // 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.
  RemoveRedundantUninitializedStrings();

  if (graph_->IsCompilingOsr() && HasPhiEquivalentAtLoopEntry(graph_)) {
    return kAnalysisFailPhiEquivalentInOsr;
  }

  if (kIsDebugBuild) {
    VerifyDuplicatePhis(graph_);
  }

  graph_->SetInSsaForm();
  return kAnalysisSuccess;
}

/**
 * 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
 * is used for floating point operations. We create a floating-point equivalent
 * constant to make the operations correctly typed.
 */
HFloatConstant* SsaBuilder::GetFloatEquivalent(HIntConstant* constant) {
  // We place the floating point constant next to this constant.
  HFloatConstant* result = constant->GetNext()->AsFloatConstantOrNull();
  if (result == nullptr) {
    float value = bit_cast<float, int32_t>(constant->GetValue());
    result = new (graph_->GetAllocator()) HFloatConstant(value);
    constant->GetBlock()->InsertInstructionBefore(result, constant->GetNext());
    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.
    DCHECK_EQ((bit_cast<int32_t, float>(result->GetValue())), constant->GetValue());
  }
  return result;
}

/**
 * Wide constants in the Dex format are not typed. So the builder types them as
 * longs, but when doing the SSA form, we might realize the constant
 * is used for floating point operations. We create a floating-point equivalent
 * constant to make the operations correctly typed.
 */
HDoubleConstant* SsaBuilder::GetDoubleEquivalent(HLongConstant* constant) {
  // We place the floating point constant next to this constant.
  HDoubleConstant* result = constant->GetNext()->AsDoubleConstantOrNull();
  if (result == nullptr) {
    double value = bit_cast<double, int64_t>(constant->GetValue());
    result = new (graph_->GetAllocator()) HDoubleConstant(value);
    constant->GetBlock()->InsertInstructionBefore(result, constant->GetNext());
    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.
    DCHECK_EQ((bit_cast<int64_t, double>(result->GetValue())), constant->GetValue());
  }
  return result;
}

/**
 * Because of Dex format, we might end up having the same phi being
 * used for non floating point operations and floating point / reference operations.
 * Because we want the graph to be correctly typed (and thereafter avoid moves between
 * floating point registers and core registers), we need to create a copy of the
 * phi with a floating point / reference type.
 */
HPhi* SsaBuilder::GetFloatDoubleOrReferenceEquivalentOfPhi(HPhi* phi, DataType::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 &&
      next->AsPhi()->GetRegNumber() == phi->GetRegNumber() &&
      next->GetType() != type) {
    // Move to the next phi to see if it is the one we are looking for.
    next = next->GetNext();
  }

  if (next == nullptr ||
      (next->AsPhi()->GetRegNumber() != phi->GetRegNumber()) ||
      (next->GetType() != type)) {
    ArenaAllocator* allocator = graph_->GetAllocator();
    HInputsRef inputs = phi->GetInputs();
    HPhi* new_phi = new (allocator) HPhi(allocator, phi->GetRegNumber(), inputs.size(), type);
    // Copy the inputs. Note that the graph may not be correctly typed
    // by doing this copy, but the type propagation phase will fix it.
    ArrayRef<HUserRecord<HInstruction*>> new_input_records = new_phi->GetInputRecords();
    for (size_t i = 0; i < inputs.size(); ++i) {
      new_input_records[i] = HUserRecord<HInstruction*>(inputs[i]);
    }
    phi->GetBlock()->InsertPhiAfter(new_phi, phi);
    DCHECK(new_phi->IsLive());
    return new_phi;
  } else {
    // An existing equivalent was found. If it is dead, conflict was previously
    // identified and we return nullptr instead.
    HPhi* next_phi = next->AsPhi();
    DCHECK_EQ(next_phi->GetType(), type);
    return next_phi->IsLive() ? next_phi : nullptr;
  }
}

HArrayGet* SsaBuilder::GetFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget) {
  DCHECK(DataType::IsIntegralType(aget->GetType()));

  if (!DataType::IsIntOrLongType(aget->GetType())) {
    // Cannot type boolean, char, byte, short to float/double.
    return nullptr;
  }

  DCHECK(ContainsElement(ambiguous_agets_, aget));
  if (agets_fixed_) {
    // This used to be an ambiguous ArrayGet but its type has been resolved to
    // int/long. Requesting a float/double equivalent should lead to a conflict.
    if (kIsDebugBuild) {
      ScopedObjectAccess soa(Thread::Current());
      DCHECK(DataType::IsIntOrLongType(GetPrimitiveArrayComponentType(aget->GetArray())));
    }
    return nullptr;
  } else {
    // This is an ambiguous ArrayGet which has not been resolved yet. Return an
    // equivalent float/double instruction to use until it is resolved.
    HArrayGet* equivalent = FindFloatOrDoubleEquivalentOfArrayGet(aget);
    return (equivalent == nullptr) ? CreateFloatOrDoubleEquivalentOfArrayGet(aget) : equivalent;
  }
}

HInstruction* SsaBuilder::GetFloatOrDoubleEquivalent(HInstruction* value, DataType::Type type) {
  if (value->IsArrayGet()) {
    return GetFloatOrDoubleEquivalentOfArrayGet(value->AsArrayGet());
  } else if (value->IsLongConstant()) {
    return GetDoubleEquivalent(value->AsLongConstant());
  } else if (value->IsIntConstant()) {
    return GetFloatEquivalent(value->AsIntConstant());
  } else if (value->IsPhi()) {
    return GetFloatDoubleOrReferenceEquivalentOfPhi(value->AsPhi(), type);
  } else {
    return nullptr;
  }
}

HInstruction* SsaBuilder::GetReferenceTypeEquivalent(HInstruction* value) {
  if (value->IsIntConstant() && value->AsIntConstant()->GetValue() == 0) {
    return graph_->GetNullConstant();
  } else if (value->IsPhi()) {
    return GetFloatDoubleOrReferenceEquivalentOfPhi(value->AsPhi(), DataType::Type::kReference);
  } else {
    return nullptr;
  }
}

}  // namespace art