ART: Do not eagerly type LoopPhi [null, ...]
ReferenceTypePropagation would eagerly set the type of each loop phi
to the type of the first input prior to beginning the fix-point
iteration. While this does make the algorithm converge faster, it
should not be applied when the first input is a NullConstant becuase
that sets the type of the phi and all dependent instructions to Object.
Bug: 25899441
Change-Id: Iff1ed26a63fe4332eaf88d9ca171e287f10ba1a6
diff --git a/compiler/optimizing/reference_type_propagation.cc b/compiler/optimizing/reference_type_propagation.cc
index 0d05c49..bcdbeec 100644
--- a/compiler/optimizing/reference_type_propagation.cc
+++ b/compiler/optimizing/reference_type_propagation.cc
@@ -127,6 +127,87 @@
}
}
+static void CheckHasNoTypedInputs(HInstruction* root_instr) {
+ ArenaAllocatorAdapter<void> adapter =
+ root_instr->GetBlock()->GetGraph()->GetArena()->Adapter(kArenaAllocReferenceTypePropagation);
+
+ ArenaVector<HPhi*> visited_phis(adapter);
+ ArenaVector<HInstruction*> worklist(adapter);
+ worklist.push_back(root_instr);
+
+ while (!worklist.empty()) {
+ HInstruction* instr = worklist.back();
+ worklist.pop_back();
+
+ if (instr->IsPhi() || instr->IsBoundType() || instr->IsNullCheck()) {
+ // Expect that both `root_instr` and its inputs have invalid RTI.
+ ScopedObjectAccess soa(Thread::Current());
+ DCHECK(!instr->GetReferenceTypeInfo().IsValid()) << "Instruction should not have valid RTI.";
+
+ // Insert all unvisited inputs to the worklist.
+ for (HInputIterator it(instr); !it.Done(); it.Advance()) {
+ HInstruction* input = it.Current();
+ if (input->IsPhi()) {
+ if (ContainsElement(visited_phis, input->AsPhi())) {
+ continue;
+ } else {
+ visited_phis.push_back(input->AsPhi());
+ }
+ }
+ worklist.push_back(input);
+ }
+ } else if (instr->IsNullConstant()) {
+ // The only input of `root_instr` allowed to have valid RTI because it is ignored.
+ } else {
+ LOG(FATAL) << "Unexpected input " << instr->DebugName() << instr->GetId() << " with RTI "
+ << instr->GetReferenceTypeInfo();
+ UNREACHABLE();
+ }
+ }
+}
+
+template<typename Functor>
+static void ForEachUntypedInstruction(HGraph* graph, Functor fn) {
+ 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);
+ }
+ }
+ for (HInstructionIterator it(block_it.Current()->GetInstructions()); !it.Done(); it.Advance()) {
+ HInstruction* instr = it.Current();
+ if (instr->GetType() == Primitive::kPrimNot && !instr->GetReferenceTypeInfo().IsValid()) {
+ fn(instr);
+ }
+ }
+ }
+}
+
+void ReferenceTypePropagation::SetUntypedInstructionsToObject() {
+ // In some cases, the fix-point iteration will leave kPrimNot instructions with
+ // invalid RTI because bytecode does not provide enough typing information.
+ // Set the RTI of such instructions to Object.
+ // Example:
+ // MyClass a = null, b = null;
+ // while (a == null) {
+ // if (cond) { a = b; } else { b = a; }
+ // }
+
+ if (kIsDebugBuild) {
+ // Test that if we are going to set RTI from invalid to Object, that
+ // instruction did not have any typed instructions in its def-use chain
+ // and therefore its type could not be inferred.
+ ForEachUntypedInstruction(graph_, [](HInstruction* instr) { CheckHasNoTypedInputs(instr); });
+ }
+
+ ReferenceTypeInfo obj_rti = ReferenceTypeInfo::Create(object_class_handle_, /* is_exact */ false);
+ ForEachUntypedInstruction(graph_, [obj_rti](HInstruction* instr) {
+ instr->SetReferenceTypeInfo(obj_rti);
+ });
+}
+
void ReferenceTypePropagation::Run() {
// To properly propagate type info we need to visit in the dominator-based order.
// Reverse post order guarantees a node's dominators are visited first.
@@ -136,6 +217,7 @@
}
ProcessWorklist();
+ SetUntypedInstructionsToObject();
ValidateTypes();
}
@@ -534,8 +616,9 @@
void RTPVisitor::VisitNullCheck(HNullCheck* instr) {
ScopedObjectAccess soa(Thread::Current());
ReferenceTypeInfo parent_rti = instr->InputAt(0)->GetReferenceTypeInfo();
- DCHECK(parent_rti.IsValid());
- instr->SetReferenceTypeInfo(parent_rti);
+ if (parent_rti.IsValid()) {
+ instr->SetReferenceTypeInfo(parent_rti);
+ }
}
void RTPVisitor::VisitFakeString(HFakeString* instr) {
@@ -588,11 +671,16 @@
}
if (phi->GetBlock()->IsLoopHeader()) {
+ ScopedObjectAccess soa(Thread::Current());
// Set the initial type for the phi. Use the non back edge input for reaching
// a fixed point faster.
+ HInstruction* first_input = phi->InputAt(0);
+ ReferenceTypeInfo first_input_rti = first_input->GetReferenceTypeInfo();
+ if (first_input_rti.IsValid() && !first_input->IsNullConstant()) {
+ phi->SetCanBeNull(first_input->CanBeNull());
+ phi->SetReferenceTypeInfo(first_input_rti);
+ }
AddToWorklist(phi);
- phi->SetCanBeNull(phi->InputAt(0)->CanBeNull());
- phi->SetReferenceTypeInfo(phi->InputAt(0)->GetReferenceTypeInfo());
} else {
// 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
@@ -683,7 +771,7 @@
instr->SetReferenceTypeInfo(parent_rti);
}
} else if (instr->IsArrayGet()) {
- // TODO: consider if it's worth "looking back" and bounding the input object
+ // TODO: consider if it's worth "looking back" and binding the input object
// to an array type.
UpdateArrayGet(instr->AsArrayGet(), handles_, object_class_handle_);
} else {
@@ -770,7 +858,10 @@
}
}
}
- instr->SetReferenceTypeInfo(new_rti);
+
+ if (new_rti.IsValid()) {
+ instr->SetReferenceTypeInfo(new_rti);
+ }
}
// Re-computes and updates the nullability of the instruction. Returns whether or
diff --git a/compiler/optimizing/reference_type_propagation.h b/compiler/optimizing/reference_type_propagation.h
index 5c05592..21789e1 100644
--- a/compiler/optimizing/reference_type_propagation.h
+++ b/compiler/optimizing/reference_type_propagation.h
@@ -57,6 +57,7 @@
SHARED_REQUIRES(Locks::mutator_lock_);
void ValidateTypes();
+ void SetUntypedInstructionsToObject();
StackHandleScopeCollection* handles_;
diff --git a/test/450-checker-types/src/Main.java b/test/450-checker-types/src/Main.java
index ec63057..cea1d5a 100644
--- a/test/450-checker-types/src/Main.java
+++ b/test/450-checker-types/src/Main.java
@@ -618,6 +618,35 @@
getSuper();
}
+ /// CHECK-START: void Main.testLoopPhiWithNullFirstInput(boolean) reference_type_propagation (after)
+ /// CHECK-DAG: <<Null:l\d+>> NullConstant
+ /// CHECK-DAG: <<Main:l\d+>> NewInstance klass:Main exact:true
+ /// CHECK-DAG: <<LoopPhi:l\d+>> Phi [<<Null>>,<<LoopPhi>>,<<Main>>] klass:Main exact:true
+ private void testLoopPhiWithNullFirstInput(boolean cond) {
+ Main a = null;
+ while (a == null) {
+ if (cond) {
+ a = new Main();
+ }
+ }
+ }
+
+ /// CHECK-START: void Main.testLoopPhisWithNullAndCrossUses(boolean) reference_type_propagation (after)
+ /// CHECK-DAG: <<Null:l\d+>> NullConstant
+ /// CHECK-DAG: <<PhiA:l\d+>> Phi [<<Null>>,<<PhiB:l\d+>>,<<PhiA>>] klass:java.lang.Object exact:false
+ /// CHECK-DAG: <<PhiB>> Phi [<<Null>>,<<PhiB>>,<<PhiA>>] klass:java.lang.Object exact:false
+ private void testLoopPhisWithNullAndCrossUses(boolean cond) {
+ Main a = null;
+ Main b = null;
+ while (a == null) {
+ if (cond) {
+ a = b;
+ } else {
+ b = a;
+ }
+ }
+ }
+
public static void main(String[] args) {
}
}
