blob: 4edadef1a4fb94fadc0406dff5c9682dd23bf051 [file] [log] [blame]
/*
* Copyright (C) 2015 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 "reference_type_propagation.h"
#include "class_linker-inl.h"
#include "mirror/class-inl.h"
#include "mirror/dex_cache.h"
#include "scoped_thread_state_change.h"
namespace art {
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.
// We take advantage of this order in `VisitBasicBlock`.
for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
VisitBasicBlock(it.Current());
}
ProcessWorklist();
}
void ReferenceTypePropagation::VisitBasicBlock(HBasicBlock* block) {
// TODO: handle other instructions that give type info
// (Call/array accesses)
// Initialize exact types first for faster convergence.
for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
HInstruction* instr = it.Current();
// TODO: Make ReferenceTypePropagation a visitor or create a new one.
if (instr->IsNewInstance()) {
VisitNewInstance(instr->AsNewInstance());
} else if (instr->IsLoadClass()) {
VisitLoadClass(instr->AsLoadClass());
} else if (instr->IsNewArray()) {
VisitNewArray(instr->AsNewArray());
} else if (instr->IsInstanceFieldGet()) {
VisitInstanceFieldGet(instr->AsInstanceFieldGet());
} else if (instr->IsStaticFieldGet()) {
VisitStaticFieldGet(instr->AsStaticFieldGet());
}
}
// Handle Phis.
for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
VisitPhi(it.Current()->AsPhi());
}
// Add extra nodes to bound types.
BoundTypeForIfNotNull(block);
BoundTypeForIfInstanceOf(block);
}
void ReferenceTypePropagation::BoundTypeForIfNotNull(HBasicBlock* block) {
HIf* ifInstruction = block->GetLastInstruction()->AsIf();
if (ifInstruction == nullptr) {
return;
}
HInstruction* ifInput = ifInstruction->InputAt(0);
if (!ifInput->IsNotEqual() && !ifInput->IsEqual()) {
return;
}
HInstruction* input0 = ifInput->InputAt(0);
HInstruction* input1 = ifInput->InputAt(1);
HInstruction* obj = nullptr;
if (input1->IsNullConstant()) {
obj = input0;
} else if (input0->IsNullConstant()) {
obj = input1;
} else {
return;
}
// We only need to bound the type if we have uses in the relevant block.
// So start with null and create the HBoundType lazily, only if it's needed.
HBoundType* bound_type = nullptr;
HBasicBlock* notNullBlock = ifInput->IsNotEqual()
? ifInstruction->IfTrueSuccessor()
: ifInstruction->IfFalseSuccessor();
for (HUseIterator<HInstruction*> it(obj->GetUses()); !it.Done(); it.Advance()) {
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());
}
user->ReplaceInput(bound_type, it.Current()->GetIndex());
}
}
}
// 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`
// to `ClassX` in the scope of the dominated blocks.
void ReferenceTypePropagation::BoundTypeForIfInstanceOf(HBasicBlock* block) {
HIf* ifInstruction = block->GetLastInstruction()->AsIf();
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 {
return;
}
// We only need to bound the type if we have uses in the relevant block.
// So start with null and create the HBoundType lazily, only if it's needed.
HBoundType* bound_type = nullptr;
HInstruction* obj = instanceOf->InputAt(0);
for (HUseIterator<HInstruction*> it(obj->GetUses()); !it.Done(); it.Advance()) {
HInstruction* user = it.Current()->GetUser();
if (instanceOfTrueBlock->Dominates(user->GetBlock())) {
if (bound_type == nullptr) {
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));
}
}
instanceOfTrueBlock->InsertInstructionBefore(
bound_type, instanceOfTrueBlock->GetFirstInstruction());
}
user->ReplaceInput(bound_type, it.Current()->GetIndex());
}
}
}
void ReferenceTypePropagation::SetClassAsTypeInfo(HInstruction* instr,
mirror::Class* klass,
bool is_exact) {
if (klass != nullptr) {
ScopedObjectAccess soa(Thread::Current());
MutableHandle<mirror::Class> handle = handles_->NewHandle(klass);
instr->SetReferenceTypeInfo(ReferenceTypeInfo::Create(handle, is_exact));
}
}
void ReferenceTypePropagation::UpdateReferenceTypeInfo(HInstruction* instr,
uint16_t type_idx,
const DexFile& dex_file,
bool is_exact) {
DCHECK_EQ(instr->GetType(), Primitive::kPrimNot);
ScopedObjectAccess soa(Thread::Current());
mirror::DexCache* dex_cache = Runtime::Current()->GetClassLinker()->FindDexCache(dex_file);
// Get type from dex cache assuming it was populated by the verifier.
SetClassAsTypeInfo(instr, dex_cache->GetResolvedType(type_idx), is_exact);
}
void ReferenceTypePropagation::VisitNewInstance(HNewInstance* instr) {
UpdateReferenceTypeInfo(instr, instr->GetTypeIndex(), instr->GetDexFile(), /* is_exact */ true);
}
void ReferenceTypePropagation::VisitNewArray(HNewArray* instr) {
UpdateReferenceTypeInfo(instr, instr->GetTypeIndex(), instr->GetDexFile(), /* is_exact */ true);
}
void ReferenceTypePropagation::UpdateFieldAccessTypeInfo(HInstruction* instr,
const FieldInfo& info) {
// The field index is unknown only during tests.
if (instr->GetType() != Primitive::kPrimNot || info.GetFieldIndex() == kUnknownFieldIndex) {
return;
}
ScopedObjectAccess soa(Thread::Current());
ClassLinker* cl = Runtime::Current()->GetClassLinker();
mirror::DexCache* dex_cache = cl->FindDexCache(info.GetDexFile());
ArtField* field = cl->GetResolvedField(info.GetFieldIndex(), dex_cache);
DCHECK(field != nullptr);
mirror::Class* klass = field->GetType<false>();
SetClassAsTypeInfo(instr, klass, /* is_exact */ false);
}
void ReferenceTypePropagation::VisitInstanceFieldGet(HInstanceFieldGet* instr) {
UpdateFieldAccessTypeInfo(instr, instr->GetFieldInfo());
}
void ReferenceTypePropagation::VisitStaticFieldGet(HStaticFieldGet* instr) {
UpdateFieldAccessTypeInfo(instr, instr->GetFieldInfo());
}
void ReferenceTypePropagation::VisitLoadClass(HLoadClass* instr) {
ScopedObjectAccess soa(Thread::Current());
mirror::DexCache* dex_cache =
Runtime::Current()->GetClassLinker()->FindDexCache(instr->GetDexFile());
// Get type from dex cache assuming it was populated by the verifier.
mirror::Class* resolved_class = dex_cache->GetResolvedType(instr->GetTypeIndex());
if (resolved_class != nullptr) {
Handle<mirror::Class> handle = handles_->NewHandle(resolved_class);
instr->SetLoadedClassRTI(ReferenceTypeInfo::Create(handle, /* is_exact */ true));
}
Handle<mirror::Class> class_handle = handles_->NewHandle(mirror::Class::GetJavaLangClass());
instr->SetReferenceTypeInfo(ReferenceTypeInfo::Create(class_handle, /* is_exact */ true));
}
void ReferenceTypePropagation::VisitPhi(HPhi* phi) {
if (phi->GetType() != Primitive::kPrimNot) {
return;
}
if (phi->GetBlock()->IsLoopHeader()) {
// Set the initial type for the phi. Use the non back edge input for reaching
// a fixed point faster.
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
// 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.
UpdateNullability(phi);
UpdateReferenceTypeInfo(phi);
}
}
ReferenceTypeInfo ReferenceTypePropagation::MergeTypes(const ReferenceTypeInfo& a,
const ReferenceTypeInfo& b) {
bool is_exact = a.IsExact() && b.IsExact();
bool is_top = a.IsTop() || b.IsTop();
Handle<mirror::Class> type_handle;
if (!is_top) {
if (a.GetTypeHandle().Get() == b.GetTypeHandle().Get()) {
type_handle = a.GetTypeHandle();
} else if (a.IsSupertypeOf(b)) {
type_handle = a.GetTypeHandle();
is_exact = false;
} else if (b.IsSupertypeOf(a)) {
type_handle = b.GetTypeHandle();
is_exact = false;
} else {
// TODO: Find a common super class.
is_top = true;
is_exact = false;
}
}
return is_top
? ReferenceTypeInfo::CreateTop(is_exact)
: ReferenceTypeInfo::Create(type_handle, is_exact);
}
bool ReferenceTypePropagation::UpdateReferenceTypeInfo(HInstruction* instr) {
ScopedObjectAccess soa(Thread::Current());
ReferenceTypeInfo previous_rti = instr->GetReferenceTypeInfo();
if (instr->IsBoundType()) {
UpdateBoundType(instr->AsBoundType());
} else if (instr->IsPhi()) {
UpdatePhi(instr->AsPhi());
} else {
LOG(FATAL) << "Invalid instruction (should not get here)";
}
return !previous_rti.IsEqual(instr->GetReferenceTypeInfo());
}
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;
}
instr->SetReferenceTypeInfo(new_rti);
}
void ReferenceTypePropagation::UpdatePhi(HPhi* instr) {
ReferenceTypeInfo new_rti = instr->InputAt(0)->GetReferenceTypeInfo();
if (new_rti.IsTop() && !new_rti.IsExact()) {
// Early return if we are Top and inexact.
instr->SetReferenceTypeInfo(new_rti);
return;
}
for (size_t i = 1; i < instr->InputCount(); i++) {
new_rti = MergeTypes(new_rti, instr->InputAt(i)->GetReferenceTypeInfo());
if (new_rti.IsTop()) {
if (!new_rti.IsExact()) {
break;
} else {
continue;
}
}
}
instr->SetReferenceTypeInfo(new_rti);
}
// 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() || instr->IsBoundType());
if (!instr->IsPhi()) {
return false;
}
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;
}
void ReferenceTypePropagation::ProcessWorklist() {
while (!worklist_.IsEmpty()) {
HInstruction* instruction = worklist_.Pop();
if (UpdateNullability(instruction) || UpdateReferenceTypeInfo(instruction)) {
AddDependentInstructionsToWorklist(instruction);
}
}
}
void ReferenceTypePropagation::AddToWorklist(HInstruction* instruction) {
DCHECK_EQ(instruction->GetType(), Primitive::kPrimNot) << instruction->GetType();
worklist_.Add(instruction);
}
void ReferenceTypePropagation::AddDependentInstructionsToWorklist(HInstruction* instruction) {
for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) {
HInstruction* user = it.Current()->GetUser();
if (user->IsPhi() || user->IsBoundType()) {
AddToWorklist(user);
}
}
}
} // namespace art