ART: Refactor SsaBuilder for more precise typing info
This reverts commit 68289a531484d26214e09f1eadd9833531a3bc3c.
Now uses Primitive::Is64BitType instead of Primitive::ComponentSize
because it was incorrectly optimized by GCC.
Bug: 26208284
Bug: 24252151
Bug: 24252100
Bug: 22538329
Bug: 25786318
Change-Id: Ib39f3da2b92bc5be5d76f4240a77567d82c6bebe
diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index 9e6cfbe..9e869e1 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -17,214 +17,11 @@
#include "ssa_builder.h"
#include "nodes.h"
-#include "primitive_type_propagation.h"
+#include "reference_type_propagation.h"
#include "ssa_phi_elimination.h"
namespace art {
-// Returns whether this is a loop header phi which was eagerly created but later
-// found inconsistent due to the vreg being undefined in one of its predecessors.
-// Such phi is marked dead and should be ignored until its removal in SsaPhiElimination.
-static bool IsUndefinedLoopHeaderPhi(HPhi* phi) {
- return phi->IsLoopHeaderPhi() && phi->InputCount() != phi->GetBlock()->GetPredecessors().size();
-}
-
-/**
- * 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 (IsUndefinedLoopHeaderPhi(phi)) {
- DCHECK(phi->IsDead());
- continue;
- }
- if (phi->IsDead() && phi->HasEnvironmentUses()) {
- phi->SetLive();
- if (block->IsLoopHeader()) {
- // Loop phis must have a type to guarantee convergence of the algorithm.
- DCHECK_NE(phi->GetType(), Primitive::kPrimVoid);
- 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 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::SetLoopHeaderPhiInputs() {
for (size_t i = loop_headers_.size(); i > 0; --i) {
HBasicBlock* block = loop_headers_[i - 1];
@@ -285,10 +82,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);
}
@@ -300,64 +98,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.
- SetLoopHeaderPhiInputs();
-
- // 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()) {
@@ -378,24 +119,345 @@
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();
+static void AddDependentInstructionsToWorklist(HInstruction* instruction,
+ ArenaVector<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 (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) {
+ HInstruction* user = it.Current()->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) {
+ 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 == input_type) {
+ // No change in type.
+ } 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;
+ }
}
- // 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
- // input types.
- dead_phis.EliminateDeadPhis();
+ // 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;
+}
- // 12) Clear locals.
+// Replace inputs of `phi` to match its type. Return false if conflict is identified.
+bool SsaBuilder::TypeInputsOfPhi(HPhi* phi, ArenaVector<HPhi*>* worklist) {
+ 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() != 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)
+ ? 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, ArenaVector<HPhi*>* worklist) {
+ 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, 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() {
+ ArenaVector<HPhi*> worklist(GetGraph()->GetArena()->Adapter());
+
+ 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()) {
+ HPhi* phi = phi_it.Current()->AsPhi();
+ if (phi->IsLive()) {
+ worklist.push_back(phi);
+ }
+ }
+ } else {
+ for (HInstructionIterator 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(ArenaVector<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) {
+ Primitive::Type type = aget->GetType();
+ DCHECK(Primitive::IsIntOrLongType(type));
+ HArrayGet* next = aget->GetNext()->AsArrayGet();
+ return (next != nullptr && next->IsEquivalentOf(aget)) ? next : nullptr;
+}
+
+static HArrayGet* CreateFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget) {
+ Primitive::Type type = aget->GetType();
+ DCHECK(Primitive::IsIntOrLongType(type));
+ DCHECK(FindFloatOrDoubleEquivalentOfArrayGet(aget) == nullptr);
+
+ HArrayGet* equivalent = new (aget->GetBlock()->GetGraph()->GetArena()) HArrayGet(
+ aget->GetArray(),
+ aget->GetIndex(),
+ type == Primitive::kPrimInt ? Primitive::kPrimFloat : Primitive::kPrimDouble,
+ aget->GetDexPc());
+ aget->GetBlock()->InsertInstructionAfter(equivalent, aget);
+ return equivalent;
+}
+
+// Returns true if the array input of `aget` is either of type int[] or long[].
+// Should only be called on ArrayGets with ambiguous type (int/float, long/double)
+// on arrays which were typed to an array class by RTP.
+static bool IsArrayGetOnIntegralArray(HArrayGet* aget) SHARED_REQUIRES(Locks::mutator_lock_) {
+ ReferenceTypeInfo array_type = aget->GetArray()->GetReferenceTypeInfo();
+ DCHECK(array_type.IsPrimitiveArrayClass());
+ ReferenceTypeInfo::TypeHandle array_type_handle = array_type.GetTypeHandle();
+
+ bool is_integral_type;
+ if (Primitive::Is64BitType(aget->GetType())) {
+ is_integral_type = array_type_handle->GetComponentType()->IsPrimitiveLong();
+ DCHECK(is_integral_type || array_type_handle->GetComponentType()->IsPrimitiveDouble());
+ } else {
+ is_integral_type = array_type_handle->GetComponentType()->IsPrimitiveInt();
+ DCHECK(is_integral_type || array_type_handle->GetComponentType()->IsPrimitiveFloat());
+ }
+ return is_integral_type;
+}
+
+bool SsaBuilder::FixAmbiguousArrayGets() {
+ if (ambiguous_agets_.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.
+ ArenaVector<HPhi*> worklist(GetGraph()->GetArena()->Adapter());
+
+ {
+ ScopedObjectAccess soa(Thread::Current());
+
+ for (HArrayGet* aget_int : ambiguous_agets_) {
+ if (!aget_int->GetArray()->GetReferenceTypeInfo().IsPrimitiveArrayClass()) {
+ // RTP did not type the input array. Bail.
+ return false;
+ }
+
+ HArrayGet* aget_float = FindFloatOrDoubleEquivalentOfArrayGet(aget_int);
+ if (IsArrayGetOnIntegralArray(aget_int)) {
+ 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 {
+ 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. This is used
+ // by GetFloatOrDoubleEquivalentOfArrayGet to report conflict.
+ agets_fixed_ = true;
+
+ if (!worklist.empty()) {
+ ProcessPrimitiveTypePropagationWorklist(&worklist);
+ EquivalentPhisCleanup();
+ }
+
+ return true;
+}
+
+BuildSsaResult 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 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();
+
+ // 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(GetGraph()).Run();
+
+ // 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();
+
+ // 6) Compute type of reference type instructions. The pass assumes that
+ // NullConstant has been fixed up.
+ ReferenceTypePropagation(GetGraph(), handles_).Run();
+
+ // 7) Step 1) duplicated ArrayGet instructions with ambiguous type (int/float
+ // or long/double). Now that RTP computed the type of the array input, the
+ // ambiguity can be resolved and the correct equivalent kept.
+ if (!FixAmbiguousArrayGets()) {
+ return kBuildSsaFailAmbiguousArrayGet;
+ }
+
+ // 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(GetGraph());
+ dead_phi_elimimation.MarkDeadPhis();
+
+ // 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
+ // 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();
+
+ // 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();
+
+ // 11) Clear locals.
for (HInstructionIterator it(GetGraph()->GetEntryBlock()->GetInstructions());
!it.Done();
it.Advance()) {
@@ -404,6 +466,8 @@
current->GetBlock()->RemoveInstruction(current);
}
}
+
+ return kBuildSsaSuccess;
}
ArenaVector<HInstruction*>* SsaBuilder::GetLocalsFor(HBasicBlock* block) {
@@ -591,6 +655,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
@@ -606,35 +672,50 @@
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 {
+ // 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);
- if (next_phi->IsDead()) {
- // TODO(dbrazdil): Remove this SetLive (we should not need to revive phis)
- // once we stop running MarkDeadPhis before PrimitiveTypePropagation. This
- // cannot revive undefined loop header phis because they cannot have uses.
- DCHECK(!IsUndefinedLoopHeaderPhi(next_phi));
- next_phi->SetLive();
- }
- return next_phi;
+ return next_phi->IsLive() ? next_phi : nullptr;
}
}
-HInstruction* SsaBuilder::GetFloatOrDoubleEquivalent(HInstruction* user,
- HInstruction* value,
- Primitive::Type type) {
+HArrayGet* SsaBuilder::GetFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget) {
+ DCHECK(Primitive::IsIntegralType(aget->GetType()));
+
+ if (!Primitive::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(IsArrayGetOnIntegralArray(aget));
+ }
+ 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, 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;
+ return GetFloatOrDoubleEquivalentOfArrayGet(value->AsArrayGet());
} else if (value->IsLongConstant()) {
return GetDoubleEquivalent(value->AsLongConstant());
} else if (value->IsIntConstant()) {
@@ -642,12 +723,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;
}
}
@@ -662,15 +738,17 @@
}
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->GetType() != value->GetType()) {
- if (load->GetType() == Primitive::kPrimFloat || load->GetType() == Primitive::kPrimDouble) {
- value = GetFloatOrDoubleEquivalent(load, value, load->GetType());
- } else if (load->GetType() == Primitive::kPrimNot) {
+ 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);
}
@@ -760,4 +838,13 @@
temp->GetBlock()->RemoveInstruction(temp);
}
+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);
+}
+
} // namespace art