Fixes and improvements in ReferenceTypePropagation
- Bound object types after a CheckCast. This increases the precision of
(inlining) generic operations.
- Make sure that the BoundType is exact when the class is final.
- Make sure that we don't duplicate BoundTypes when we run the analysis
more than once.
Change-Id: Ic22b610766fae101f942c0d753ddcac32ac1844a
diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc
index 37c060c..aaf7a6d 100644
--- a/compiler/optimizing/graph_visualizer.cc
+++ b/compiler/optimizing/graph_visualizer.cc
@@ -397,6 +397,11 @@
return strcmp(pass_name_, name) == 0;
}
+ bool IsReferenceTypePropagationPass() {
+ return strstr(pass_name_, ReferenceTypePropagation::kReferenceTypePropagationPassName)
+ != nullptr;
+ }
+
void PrintInstruction(HInstruction* instruction) {
output_ << instruction->DebugName();
if (instruction->InputCount() > 0) {
@@ -460,14 +465,13 @@
} else {
StartAttributeStream("loop") << "B" << info->GetHeader()->GetBlockId();
}
- } else if (IsPass(ReferenceTypePropagation::kReferenceTypePropagationPassName)
- && is_after_pass_) {
+ } else if (IsReferenceTypePropagationPass() && is_after_pass_) {
if (instruction->GetType() == Primitive::kPrimNot) {
if (instruction->IsLoadClass()) {
ReferenceTypeInfo info = instruction->AsLoadClass()->GetLoadedClassRTI();
ScopedObjectAccess soa(Thread::Current());
if (info.GetTypeHandle().GetReference() != nullptr) {
- StartAttributeStream("klass") << PrettyClass(info.GetTypeHandle().Get());
+ StartAttributeStream("klass") << PrettyDescriptor(info.GetTypeHandle().Get());
} else {
StartAttributeStream("klass") << "unresolved";
}
@@ -477,7 +481,7 @@
StartAttributeStream("klass") << "java.lang.Object";
} else {
ScopedObjectAccess soa(Thread::Current());
- StartAttributeStream("klass") << PrettyClass(info.GetTypeHandle().Get());
+ StartAttributeStream("klass") << PrettyDescriptor(info.GetTypeHandle().Get());
}
StartAttributeStream("exact") << std::boolalpha << info.IsExact() << std::noboolalpha;
}
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 8546a10..57c7829 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -1488,6 +1488,7 @@
// Does not apply for all instructions, but having this at top level greatly
// simplifies the null check elimination.
+ // TODO: Consider merging can_be_null into ReferenceTypeInfo.
virtual bool CanBeNull() const {
DCHECK_EQ(GetType(), Primitive::kPrimNot) << "CanBeNull only applies to reference types";
return true;
@@ -4070,27 +4071,39 @@
class HBoundType : public HExpression<1> {
public:
- HBoundType(HInstruction* input, ReferenceTypeInfo bound_type)
+ HBoundType(HInstruction* input, ReferenceTypeInfo upper_bound, bool upper_can_be_null)
: HExpression(Primitive::kPrimNot, SideEffects::None()),
- bound_type_(bound_type) {
+ upper_bound_(upper_bound),
+ upper_can_be_null_(upper_can_be_null) {
DCHECK_EQ(input->GetType(), Primitive::kPrimNot);
SetRawInputAt(0, input);
}
- const ReferenceTypeInfo& GetBoundType() const { return bound_type_; }
+ // GetUpper* should only be used in reference type propagation.
+ const ReferenceTypeInfo& GetUpperBound() const { return upper_bound_; }
+ bool GetUpperCanBeNull() const { return upper_can_be_null_; }
- bool CanBeNull() const OVERRIDE {
- // `null instanceof ClassX` always return false so we can't be null.
- return false;
+ void SetCanBeNull(bool can_be_null) {
+ DCHECK(upper_can_be_null_ || !can_be_null);
+ can_be_null_ = can_be_null;
}
+ bool CanBeNull() const OVERRIDE { return can_be_null_; }
+
DECLARE_INSTRUCTION(BoundType);
private:
// Encodes the most upper class that this instruction can have. In other words
- // it is always the case that GetBoundType().IsSupertypeOf(GetReferenceType()).
- // It is used to bound the type in cases like `if (x instanceof ClassX) {}`
- const ReferenceTypeInfo bound_type_;
+ // it is always the case that GetUpperBound().IsSupertypeOf(GetReferenceType()).
+ // It is used to bound the type in cases like:
+ // if (x instanceof ClassX) {
+ // // uper_bound_ will be ClassX
+ // }
+ const ReferenceTypeInfo upper_bound_;
+ // Represents the top constraint that can_be_null_ cannot exceed (i.e. if this
+ // is false then can_be_null_ cannot be true).
+ const bool upper_can_be_null_;
+ bool can_be_null_;
DISALLOW_COPY_AND_ASSIGN(HBoundType);
};
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 4568a46..ae1958a 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -379,7 +379,8 @@
InstructionSimplifier* simplify3 = new (arena) InstructionSimplifier(
graph, stats, "instruction_simplifier_after_bce");
ReferenceTypePropagation* type_propagation2 =
- new (arena) ReferenceTypePropagation(graph, handles);
+ new (arena) ReferenceTypePropagation(
+ graph, handles, "reference_type_propagation_after_inlining");
InstructionSimplifier* simplify4 = new (arena) InstructionSimplifier(
graph, stats, "instruction_simplifier_before_codegen");
diff --git a/compiler/optimizing/reference_type_propagation.cc b/compiler/optimizing/reference_type_propagation.cc
index 68316c2..84db62b 100644
--- a/compiler/optimizing/reference_type_propagation.cc
+++ b/compiler/optimizing/reference_type_propagation.cc
@@ -38,6 +38,7 @@
void VisitStaticFieldGet(HStaticFieldGet* instr) OVERRIDE;
void VisitInvoke(HInvoke* instr) OVERRIDE;
void VisitArrayGet(HArrayGet* instr) OVERRIDE;
+ void VisitCheckCast(HCheckCast* instr) OVERRIDE;
void UpdateReferenceTypeInfo(HInstruction* instr,
uint16_t type_idx,
const DexFile& dex_file,
@@ -78,6 +79,72 @@
BoundTypeForIfInstanceOf(block);
}
+// Create a bound type for the given object narrowing the type as much as possible.
+// The BoundType upper values for the super type and can_be_null will be taken from
+// load_class.GetLoadedClassRTI() and upper_can_be_null.
+static HBoundType* CreateBoundType(ArenaAllocator* arena,
+ HInstruction* obj,
+ HLoadClass* load_class,
+ bool upper_can_be_null)
+ SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+ ReferenceTypeInfo obj_rti = obj->GetReferenceTypeInfo();
+ ReferenceTypeInfo class_rti = load_class->GetLoadedClassRTI();
+ HBoundType* bound_type = new (arena) HBoundType(obj, class_rti, upper_can_be_null);
+ // Narrow the type as much as possible.
+ if (load_class->IsResolved() && class_rti.GetTypeHandle()->IsFinal()) {
+ bound_type->SetReferenceTypeInfo(
+ ReferenceTypeInfo::Create(class_rti.GetTypeHandle(), /* is_exact */ true));
+ } else if (!load_class->IsResolved() || class_rti.IsSupertypeOf(obj_rti)) {
+ bound_type->SetReferenceTypeInfo(obj_rti);
+ } else {
+ bound_type->SetReferenceTypeInfo(
+ ReferenceTypeInfo::Create(class_rti.GetTypeHandle(), /* is_exact */ false));
+ }
+ return bound_type;
+}
+
+// Check if we should create a bound type for the given object at the specified
+// position. Because of inlining and the fact we run RTP more than once and we
+// might have a HBoundType already. If we do, we should not create a new one.
+// In this case we also assert that there are no other uses of the object (except
+// the bound type) dominated by the specified dominator_instr or dominator_block.
+static bool ShouldCreateBoundType(HInstruction* position,
+ HInstruction* obj,
+ ReferenceTypeInfo upper_bound,
+ HInstruction* dominator_instr,
+ HBasicBlock* dominator_block)
+ SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+ // If the position where we should insert the bound type is not already a
+ // a bound type then we need to create one.
+ if (position == nullptr || !position->IsBoundType()) {
+ return true;
+ }
+
+ HBoundType* existing_bound_type = position->AsBoundType();
+ if (existing_bound_type->GetUpperBound().IsSupertypeOf(upper_bound)) {
+ if (kIsDebugBuild) {
+ // Check that the existing HBoundType dominates all the uses.
+ for (HUseIterator<HInstruction*> it(obj->GetUses()); !it.Done(); it.Advance()) {
+ HInstruction* user = it.Current()->GetUser();
+ if (dominator_instr != nullptr) {
+ DCHECK(!dominator_instr->StrictlyDominates(user)
+ || user == existing_bound_type
+ || existing_bound_type->StrictlyDominates(user));
+ } else if (dominator_block != nullptr) {
+ DCHECK(!dominator_block->Dominates(user->GetBlock())
+ || user == existing_bound_type
+ || existing_bound_type->StrictlyDominates(user));
+ }
+ }
+ }
+ } else {
+ // TODO: if the current bound type is a refinement we could update the
+ // existing_bound_type with the a new upper limit. However, we also need to
+ // update its users and have access to the work list.
+ }
+ return false;
+}
+
void ReferenceTypePropagation::BoundTypeForIfNotNull(HBasicBlock* block) {
HIf* ifInstruction = block->GetLastInstruction()->AsIf();
if (ifInstruction == nullptr) {
@@ -116,8 +183,19 @@
HInstruction* user = it.Current()->GetUser();
if (notNullBlock->Dominates(user->GetBlock())) {
if (bound_type == nullptr) {
- bound_type = new (graph_->GetArena()) HBoundType(obj, ReferenceTypeInfo::CreateTop(false));
- notNullBlock->InsertInstructionBefore(bound_type, notNullBlock->GetFirstInstruction());
+ ScopedObjectAccess soa(Thread::Current());
+ HInstruction* insert_point = notNullBlock->GetFirstInstruction();
+ ReferenceTypeInfo object_rti = ReferenceTypeInfo::CreateTop(false);
+ if (ShouldCreateBoundType(insert_point, obj, object_rti, nullptr, notNullBlock)) {
+ bound_type = new (graph_->GetArena()) HBoundType(
+ obj, object_rti, /* bound_can_be_null */ false);
+ notNullBlock->InsertInstructionBefore(bound_type, insert_point);
+ } else {
+ // We already have a bound type on the position we would need to insert
+ // the new one. The existing bound type should dominate all the users
+ // (dchecked) so there's no need to continue.
+ break;
+ }
}
user->ReplaceInput(bound_type, it.Current()->GetIndex());
}
@@ -171,25 +249,23 @@
HInstruction* user = it.Current()->GetUser();
if (instanceOfTrueBlock->Dominates(user->GetBlock())) {
if (bound_type == nullptr) {
+ ScopedObjectAccess soa(Thread::Current());
HLoadClass* load_class = instanceOf->InputAt(1)->AsLoadClass();
-
- ReferenceTypeInfo obj_rti = obj->GetReferenceTypeInfo();
ReferenceTypeInfo class_rti = load_class->GetLoadedClassRTI();
- bound_type = new (graph_->GetArena()) HBoundType(obj, class_rti);
-
- // Narrow the type as much as possible.
- {
- ScopedObjectAccess soa(Thread::Current());
- if (!load_class->IsResolved() || class_rti.IsSupertypeOf(obj_rti)) {
- bound_type->SetReferenceTypeInfo(obj_rti);
- } else {
- bound_type->SetReferenceTypeInfo(
- ReferenceTypeInfo::Create(class_rti.GetTypeHandle(), /* is_exact */ false));
- }
+ HInstruction* insert_point = instanceOfTrueBlock->GetFirstInstruction();
+ if (ShouldCreateBoundType(insert_point, obj, class_rti, nullptr, instanceOfTrueBlock)) {
+ bound_type = CreateBoundType(
+ graph_->GetArena(),
+ obj,
+ load_class,
+ false /* InstanceOf ensures the object is not null. */);
+ instanceOfTrueBlock->InsertInstructionBefore(bound_type, insert_point);
+ } else {
+ // We already have a bound type on the position we would need to insert
+ // the new one. The existing bound type should dominate all the users
+ // (dchecked) so there's no need to continue.
+ break;
}
-
- instanceOfTrueBlock->InsertInstructionBefore(
- bound_type, instanceOfTrueBlock->GetFirstInstruction());
}
user->ReplaceInput(bound_type, it.Current()->GetIndex());
}
@@ -266,6 +342,35 @@
instr->SetReferenceTypeInfo(ReferenceTypeInfo::Create(class_handle, /* is_exact */ true));
}
+void RTPVisitor::VisitCheckCast(HCheckCast* check_cast) {
+ HInstruction* obj = check_cast->InputAt(0);
+ HBoundType* bound_type = nullptr;
+ for (HUseIterator<HInstruction*> it(obj->GetUses()); !it.Done(); it.Advance()) {
+ HInstruction* user = it.Current()->GetUser();
+ if (check_cast->StrictlyDominates(user)) {
+ if (bound_type == nullptr) {
+ ScopedObjectAccess soa(Thread::Current());
+ HLoadClass* load_class = check_cast->InputAt(1)->AsLoadClass();
+ ReferenceTypeInfo class_rti = load_class->GetLoadedClassRTI();
+ if (ShouldCreateBoundType(check_cast->GetNext(), obj, class_rti, check_cast, nullptr)) {
+ bound_type = CreateBoundType(
+ GetGraph()->GetArena(),
+ obj,
+ load_class,
+ true /* CheckCast succeeds for nulls. */);
+ check_cast->GetBlock()->InsertInstructionAfter(bound_type, check_cast);
+ } else {
+ // We already have a bound type on the position we would need to insert
+ // the new one. The existing bound type should dominate all the users
+ // (dchecked) so there's no need to continue.
+ break;
+ }
+ }
+ user->ReplaceInput(bound_type, it.Current()->GetIndex());
+ }
+ }
+}
+
void ReferenceTypePropagation::VisitPhi(HPhi* phi) {
if (phi->GetType() != Primitive::kPrimNot) {
return;
@@ -362,9 +467,9 @@
void ReferenceTypePropagation::UpdateBoundType(HBoundType* instr) {
ReferenceTypeInfo new_rti = instr->InputAt(0)->GetReferenceTypeInfo();
// Be sure that we don't go over the bounded type.
- ReferenceTypeInfo bound_rti = instr->GetBoundType();
- if (!bound_rti.IsSupertypeOf(new_rti)) {
- new_rti = bound_rti;
+ ReferenceTypeInfo upper_bound_rti = instr->GetUpperBound();
+ if (!upper_bound_rti.IsSupertypeOf(new_rti)) {
+ new_rti = upper_bound_rti;
}
instr->SetReferenceTypeInfo(new_rti);
}
@@ -394,19 +499,22 @@
bool ReferenceTypePropagation::UpdateNullability(HInstruction* instr) {
DCHECK(instr->IsPhi() || instr->IsBoundType());
- if (!instr->IsPhi()) {
- return false;
+ bool existing_can_be_null = instr->CanBeNull();
+ if (instr->IsPhi()) {
+ HPhi* phi = instr->AsPhi();
+ bool new_can_be_null = false;
+ for (size_t i = 0; i < phi->InputCount(); i++) {
+ if (phi->InputAt(i)->CanBeNull()) {
+ new_can_be_null = true;
+ break;
+ }
+ }
+ phi->SetCanBeNull(new_can_be_null);
+ } else if (instr->IsBoundType()) {
+ HBoundType* bound_type = instr->AsBoundType();
+ bound_type->SetCanBeNull(instr->InputAt(0)->CanBeNull() && bound_type->GetUpperCanBeNull());
}
-
- HPhi* phi = instr->AsPhi();
- bool existing_can_be_null = phi->CanBeNull();
- bool new_can_be_null = false;
- for (size_t i = 0; i < phi->InputCount(); i++) {
- new_can_be_null |= phi->InputAt(i)->CanBeNull();
- }
- phi->SetCanBeNull(new_can_be_null);
-
- return existing_can_be_null != new_can_be_null;
+ return existing_can_be_null != instr->CanBeNull();
}
void ReferenceTypePropagation::ProcessWorklist() {
diff --git a/compiler/optimizing/reference_type_propagation.h b/compiler/optimizing/reference_type_propagation.h
index 17cfed4..e8680ea 100644
--- a/compiler/optimizing/reference_type_propagation.h
+++ b/compiler/optimizing/reference_type_propagation.h
@@ -30,8 +30,10 @@
*/
class ReferenceTypePropagation : public HOptimization {
public:
- ReferenceTypePropagation(HGraph* graph, StackHandleScopeCollection* handles)
- : HOptimization(graph, kReferenceTypePropagationPassName),
+ ReferenceTypePropagation(HGraph* graph,
+ StackHandleScopeCollection* handles,
+ const char* name = kReferenceTypePropagationPassName)
+ : HOptimization(graph, name),
handles_(handles),
worklist_(graph->GetArena(), kDefaultWorklistSize) {}
diff --git a/test/450-checker-types/src/Main.java b/test/450-checker-types/src/Main.java
index 9070627..67060d9 100644
--- a/test/450-checker-types/src/Main.java
+++ b/test/450-checker-types/src/Main.java
@@ -14,7 +14,6 @@
* limitations under the License.
*/
-
interface Interface {
void $noinline$f();
}
@@ -52,6 +51,15 @@
}
}
+class Generic<A> {
+ private A a = null;
+ public A get() {
+ return a;
+ }
+}
+
+final class Final {}
+
public class Main {
/// CHECK-START: void Main.testSimpleRemove() instruction_simplifier_after_types (before)
@@ -395,6 +403,67 @@
((SubclassA)a[0]).$noinline$g();
}
+ private Generic<SubclassC> genericC = new Generic<SubclassC>();
+ private Generic<Final> genericFinal = new Generic<Final>();
+
+ private SubclassC get() {
+ return genericC.get();
+ }
+
+ private Final getFinal() {
+ return genericFinal.get();
+ }
+
+ /// CHECK-START: SubclassC Main.inlineGenerics() reference_type_propagation (after)
+ /// CHECK: <<Invoke:l\d+>> InvokeStaticOrDirect klass:SubclassC
+ /// CHECK-NEXT: Return [<<Invoke>>]
+
+ /// CHECK-START: SubclassC Main.inlineGenerics() reference_type_propagation_after_inlining (after)
+ /// CHECK: <<BoundType:l\d+>> BoundType klass:SubclassC
+ /// CHECK: Return [<<BoundType>>]
+ private SubclassC inlineGenerics() {
+ SubclassC c = get();
+ return c;
+ }
+
+ /// CHECK-START: Final Main.inlineGenericsFinal() reference_type_propagation (after)
+ /// CHECK: <<Invoke:l\d+>> InvokeStaticOrDirect klass:Final exact:true
+ /// CHECK-NEXT: Return [<<Invoke>>]
+
+ /// CHECK-START: Final Main.inlineGenericsFinal() reference_type_propagation_after_inlining (after)
+ /// CHECK: <<BoundType:l\d+>> BoundType klass:Final exact:true
+ /// CHECK: Return [<<BoundType>>]
+ private Final inlineGenericsFinal() {
+ Final f = getFinal();
+ return f;
+ }
+
+ /// CHECK-START: void Main.boundOnlyOnceIfNotNull(java.lang.Object) reference_type_propagation_after_inlining (after)
+ /// CHECK: BoundType
+ /// CHECK-NOT: BoundType
+ private void boundOnlyOnceIfNotNull(Object o) {
+ if (o != null) {
+ o.toString();
+ }
+ }
+
+ /// CHECK-START: void Main.boundOnlyOnceIfInstanceOf(java.lang.Object) reference_type_propagation_after_inlining (after)
+ /// CHECK: BoundType
+ /// CHECK-NOT: BoundType
+ private void boundOnlyOnceIfInstanceOf(Object o) {
+ if (o instanceof Main) {
+ o.toString();
+ }
+ }
+
+ /// CHECK-START: Final Main.boundOnlyOnceCheckCast(Generic) reference_type_propagation_after_inlining (after)
+ /// CHECK: BoundType
+ /// CHECK-NOT: BoundType
+ private Final boundOnlyOnceCheckCast(Generic<Final> o) {
+ Final f = o.get();
+ return f;
+ }
+
public static void main(String[] args) {
}
}