ART: Refactor SsaBuilder for more precise typing info
This patch refactors the SsaBuilder to do the following:
1) All phis are constructed live and marked dead if not used or proved
to be conflicting.
2) Primitive type propagation, now not a separate pass, identifies
conflicting types and marks corresponding phis dead.
3) When compiling --debuggable, DeadPhiHandling used to revive phis
which had only environmental uses but did not attempt to resolve
conflicts. This pass was removed as obsolete and is now superseded
by primitive type propagation (identifying conflicting phis) and
SsaDeadPhiEliminiation (keeping phis live if debuggable + env use).
4) Resolving conflicts requires correct primitive type information
on all instructions. This was not the case for ArrayGet instructions
which can have ambiguous types in the bytecode. To this end,
SsaBuilder now runs reference type propagation and types ArrayGets
from the type of the input array.
5) With RTP being run inside the SsaBuilder, it is not necessary to
run it as a separate optimization pass. Optimizations can now assume
that all instructions of type kPrimNot have reference type info after
SsaBuilder (with the exception of NullConstant).
6) Graph now contains a reference type to be assigned to NullConstant.
All reference type instructions therefore have RTI, as now enforced
by the SsaChecker.
Bug: 24252151
Bug: 24252100
Bug: 22538329
Bug: 25786318
Change-Id: I7a3aee1ff66c82d64b4846611c547af17e91d260
diff --git a/compiler/optimizing/reference_type_propagation.cc b/compiler/optimizing/reference_type_propagation.cc
index fea903d..94a297c 100644
--- a/compiler/optimizing/reference_type_propagation.cc
+++ b/compiler/optimizing/reference_type_propagation.cc
@@ -40,7 +40,6 @@
throwable_class_handle_(throwable_class_handle),
worklist_(worklist) {}
- void VisitNullConstant(HNullConstant* null_constant) OVERRIDE;
void VisitNewInstance(HNewInstance* new_instance) OVERRIDE;
void VisitLoadClass(HLoadClass* load_class) OVERRIDE;
void VisitClinitCheck(HClinitCheck* clinit_check) OVERRIDE;
@@ -71,8 +70,6 @@
ReferenceTypeInfo::TypeHandle string_class_handle_;
ReferenceTypeInfo::TypeHandle throwable_class_handle_;
ArenaVector<HInstruction*>* worklist_;
-
- static constexpr size_t kDefaultWorklistSize = 8;
};
ReferenceTypePropagation::ReferenceTypePropagation(HGraph* graph,
@@ -171,9 +168,13 @@
ScopedObjectAccess soa(Thread::Current());
for (HReversePostOrderIterator block_it(*graph); !block_it.Done(); block_it.Advance()) {
for (HInstructionIterator it(block_it.Current()->GetPhis()); !it.Done(); it.Advance()) {
- HInstruction* instr = it.Current();
- if (instr->GetType() == Primitive::kPrimNot && !instr->GetReferenceTypeInfo().IsValid()) {
- fn(instr);
+ HPhi* phi = it.Current()->AsPhi();
+ // Note that the graph may contain dead phis when run from the SsaBuilder.
+ // Skip those as they might have a type conflict and will be removed anyway.
+ if (phi->IsLive() &&
+ phi->GetType() == Primitive::kPrimNot &&
+ !phi->GetReferenceTypeInfo().IsValid()) {
+ fn(phi);
}
}
for (HInstructionIterator it(block_it.Current()->GetInstructions()); !it.Done(); it.Advance()) {
@@ -376,6 +377,75 @@
}
}
+// Returns true if one of the patterns below has been recognized. If so, the
+// InstanceOf instruction together with the true branch of `ifInstruction` will
+// be returned using the out parameters.
+// Recognized patterns:
+// (1) patterns equivalent to `if (obj instanceof X)`
+// (a) InstanceOf -> Equal to 1 -> If
+// (b) InstanceOf -> NotEqual to 0 -> If
+// (c) InstanceOf -> If
+// (2) patterns equivalent to `if (!(obj instanceof X))`
+// (a) InstanceOf -> Equal to 0 -> If
+// (b) InstanceOf -> NotEqual to 1 -> If
+// (c) InstanceOf -> BooleanNot -> If
+static bool MatchIfInstanceOf(HIf* ifInstruction,
+ /* out */ HInstanceOf** instanceOf,
+ /* out */ HBasicBlock** trueBranch) {
+ HInstruction* input = ifInstruction->InputAt(0);
+
+ if (input->IsEqual()) {
+ HInstruction* rhs = input->AsEqual()->GetConstantRight();
+ if (rhs != nullptr) {
+ HInstruction* lhs = input->AsEqual()->GetLeastConstantLeft();
+ if (lhs->IsInstanceOf() && rhs->IsIntConstant()) {
+ if (rhs->AsIntConstant()->IsOne()) {
+ // Case (1a)
+ *trueBranch = ifInstruction->IfTrueSuccessor();
+ } else {
+ // Case (2a)
+ DCHECK(rhs->AsIntConstant()->IsZero());
+ *trueBranch = ifInstruction->IfFalseSuccessor();
+ }
+ *instanceOf = lhs->AsInstanceOf();
+ return true;
+ }
+ }
+ } else if (input->IsNotEqual()) {
+ HInstruction* rhs = input->AsNotEqual()->GetConstantRight();
+ if (rhs != nullptr) {
+ HInstruction* lhs = input->AsNotEqual()->GetLeastConstantLeft();
+ if (lhs->IsInstanceOf() && rhs->IsIntConstant()) {
+ if (rhs->AsIntConstant()->IsZero()) {
+ // Case (1b)
+ *trueBranch = ifInstruction->IfTrueSuccessor();
+ } else {
+ // Case (2b)
+ DCHECK(rhs->AsIntConstant()->IsOne());
+ *trueBranch = ifInstruction->IfFalseSuccessor();
+ }
+ *instanceOf = lhs->AsInstanceOf();
+ return true;
+ }
+ }
+ } else if (input->IsInstanceOf()) {
+ // Case (1c)
+ *instanceOf = input->AsInstanceOf();
+ *trueBranch = ifInstruction->IfTrueSuccessor();
+ return true;
+ } else if (input->IsBooleanNot()) {
+ HInstruction* not_input = input->InputAt(0);
+ if (not_input->IsInstanceOf()) {
+ // Case (2c)
+ *instanceOf = not_input->AsInstanceOf();
+ *trueBranch = ifInstruction->IfFalseSuccessor();
+ return true;
+ }
+ }
+
+ return false;
+}
+
// Detects if `block` is the True block for the pattern
// `if (x instanceof ClassX) { }`
// If that's the case insert an HBoundType instruction to bound the type of `x`
@@ -385,22 +455,11 @@
if (ifInstruction == nullptr) {
return;
}
- HInstruction* ifInput = ifInstruction->InputAt(0);
- HInstruction* instanceOf = nullptr;
- HBasicBlock* instanceOfTrueBlock = nullptr;
- // The instruction simplifier has transformed:
- // - `if (a instanceof A)` into an HIf with an HInstanceOf input
- // - `if (!(a instanceof A)` into an HIf with an HBooleanNot input (which in turn
- // has an HInstanceOf input)
- // So we should not see the usual HEqual here.
- if (ifInput->IsInstanceOf()) {
- instanceOf = ifInput;
- instanceOfTrueBlock = ifInstruction->IfTrueSuccessor();
- } else if (ifInput->IsBooleanNot() && ifInput->InputAt(0)->IsInstanceOf()) {
- instanceOf = ifInput->InputAt(0);
- instanceOfTrueBlock = ifInstruction->IfFalseSuccessor();
- } else {
+ // Try to recognize common `if (instanceof)` and `if (!instanceof)` patterns.
+ HInstanceOf* instanceOf = nullptr;
+ HBasicBlock* instanceOfTrueBlock = nullptr;
+ if (!MatchIfInstanceOf(ifInstruction, &instanceOf, &instanceOfTrueBlock)) {
return;
}
@@ -505,13 +564,6 @@
SetClassAsTypeInfo(instr, dex_cache->GetResolvedType(type_idx), is_exact);
}
-void RTPVisitor::VisitNullConstant(HNullConstant* instr) {
- // TODO: The null constant could be bound contextually (e.g. based on return statements)
- // to a more precise type.
- instr->SetReferenceTypeInfo(
- ReferenceTypeInfo::Create(object_class_handle_, /* is_exact */ false));
-}
-
void RTPVisitor::VisitNewInstance(HNewInstance* instr) {
UpdateReferenceTypeInfo(instr, instr->GetTypeIndex(), instr->GetDexFile(), /* is_exact */ true);
}
@@ -523,7 +575,11 @@
static mirror::Class* GetClassFromDexCache(Thread* self, const DexFile& dex_file, uint16_t type_idx)
SHARED_REQUIRES(Locks::mutator_lock_) {
mirror::DexCache* dex_cache =
- Runtime::Current()->GetClassLinker()->FindDexCache(self, dex_file, false);
+ Runtime::Current()->GetClassLinker()->FindDexCache(self, dex_file, /* allow_failure */ true);
+ if (dex_cache == nullptr) {
+ // Dex cache could not be found. This should only happen during gtests.
+ return nullptr;
+ }
// Get type from dex cache assuming it was populated by the verifier.
return dex_cache->GetResolvedType(type_idx);
}
@@ -540,17 +596,24 @@
void RTPVisitor::UpdateFieldAccessTypeInfo(HInstruction* instr,
const FieldInfo& info) {
- // The field index is unknown only during tests.
- if (instr->GetType() != Primitive::kPrimNot || info.GetFieldIndex() == kUnknownFieldIndex) {
+ if (instr->GetType() != Primitive::kPrimNot) {
return;
}
ScopedObjectAccess soa(Thread::Current());
- ClassLinker* cl = Runtime::Current()->GetClassLinker();
- ArtField* field = cl->GetResolvedField(info.GetFieldIndex(), info.GetDexCache().Get());
- // TODO: There are certain cases where we can't resolve the field.
- // b/21914925 is open to keep track of a repro case for this issue.
- mirror::Class* klass = (field == nullptr) ? nullptr : field->GetType<false>();
+ mirror::Class* klass = nullptr;
+
+ // The field index is unknown only during tests.
+ if (info.GetFieldIndex() != kUnknownFieldIndex) {
+ ClassLinker* cl = Runtime::Current()->GetClassLinker();
+ ArtField* field = cl->GetResolvedField(info.GetFieldIndex(), info.GetDexCache().Get());
+ // TODO: There are certain cases where we can't resolve the field.
+ // b/21914925 is open to keep track of a repro case for this issue.
+ if (field != nullptr) {
+ klass = field->GetType<false>();
+ }
+ }
+
SetClassAsTypeInfo(instr, klass, /* is_exact */ false);
}
@@ -666,7 +729,7 @@
}
void ReferenceTypePropagation::VisitPhi(HPhi* phi) {
- if (phi->GetType() != Primitive::kPrimNot) {
+ if (phi->IsDead() || phi->GetType() != Primitive::kPrimNot) {
return;
}
@@ -824,6 +887,8 @@
// NullConstant inputs are ignored during merging as they do not provide any useful information.
// If all the inputs are NullConstants then the type of the phi will be set to Object.
void ReferenceTypePropagation::UpdatePhi(HPhi* instr) {
+ DCHECK(instr->IsLive());
+
size_t input_count = instr->InputCount();
size_t first_input_index_not_null = 0;
while (first_input_index_not_null < input_count &&
@@ -868,7 +933,7 @@
// Re-computes and updates the nullability of the instruction. Returns whether or
// not the nullability was changed.
bool ReferenceTypePropagation::UpdateNullability(HInstruction* instr) {
- DCHECK(instr->IsPhi()
+ DCHECK((instr->IsPhi() && instr->AsPhi()->IsLive())
|| instr->IsBoundType()
|| instr->IsNullCheck()
|| instr->IsArrayGet());
@@ -916,7 +981,7 @@
void ReferenceTypePropagation::AddDependentInstructionsToWorklist(HInstruction* instruction) {
for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) {
HInstruction* user = it.Current()->GetUser();
- if (user->IsPhi()
+ if ((user->IsPhi() && user->AsPhi()->IsLive())
|| user->IsBoundType()
|| user->IsNullCheck()
|| (user->IsArrayGet() && (user->GetType() == Primitive::kPrimNot))) {