compiler/optimizing/reference_type_propagation.cc

   1 /*
   2  * Copyright (C) 2015 The Android Open Source Project
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include "reference_type_propagation.h"
  18
  19 #include "class_linker-inl.h"
  20 #include "mirror/class-inl.h"
  21 #include "mirror/dex_cache.h"
  22 #include "scoped_thread_state_change.h"
  23
  24 namespace art {
  25
  26 void ReferenceTypePropagation::Run() {
  27   // To properly propagate type info we need to visit in the dominator-based order.
  28   // Reverse post order guarantees a node's dominators are visited first.
  29   // We take advantage of this order in `VisitBasicBlock`.
  30   for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
  31     VisitBasicBlock(it.Current());
  32   }
  33   ProcessWorklist();
  34 }
  35
  36 void ReferenceTypePropagation::VisitBasicBlock(HBasicBlock* block) {
  37   // TODO: handle other instructions that give type info
  38   // (NewArray/Call/Field accesses/array accesses)
  39
  40   // Initialize exact types first for faster convergence.
  41   for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
  42     HInstruction* instr = it.Current();
  43     if (instr->IsNewInstance()) {
  44       VisitNewInstance(instr->AsNewInstance());
  45     } else if (instr->IsLoadClass()) {
  46       VisitLoadClass(instr->AsLoadClass());
  47     }
  48   }
  49
  50   // Handle Phis.
  51   for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
  52     VisitPhi(it.Current()->AsPhi());
  53   }
  54
  55   // Add extra nodes to bound types.
  56   BoundTypeForIfNotNull(block);
  57   BoundTypeForIfInstanceOf(block);
  58 }
  59
  60 void ReferenceTypePropagation::BoundTypeForIfNotNull(HBasicBlock* block) {
  61   HIf* ifInstruction = block->GetLastInstruction()->AsIf();
  62   if (ifInstruction == nullptr) {
  63     return;
  64   }
  65   HInstruction* ifInput = ifInstruction->InputAt(0);
  66   if (!ifInput->IsNotEqual() && !ifInput->IsEqual()) {
  67     return;
  68   }
  69   HInstruction* input0 = ifInput->InputAt(0);
  70   HInstruction* input1 = ifInput->InputAt(1);
  71   HInstruction* obj = nullptr;
  72
  73   if (input1->IsNullConstant()) {
  74     obj = input0;
  75   } else if (input0->IsNullConstant()) {
  76     obj = input1;
  77   } else {
  78     return;
  79   }
  80
  81   if (!obj->CanBeNull() || obj->IsNullConstant()) {
  82     // Null check is dead code and will be removed by DCE.
  83     return;
  84   }
  85   DCHECK(!obj->IsLoadClass()) << "We should not replace HLoadClass instructions";
  86
  87   // We only need to bound the type if we have uses in the relevant block.
  88   // So start with null and create the HBoundType lazily, only if it's needed.
  89   HBoundType* bound_type = nullptr;
  90   HBasicBlock* notNullBlock = ifInput->IsNotEqual()
  91       ? ifInstruction->IfTrueSuccessor()
  92       : ifInstruction->IfFalseSuccessor();
  93
  94   for (HUseIterator<HInstruction*> it(obj->GetUses()); !it.Done(); it.Advance()) {
  95     HInstruction* user = it.Current()->GetUser();
  96     if (notNullBlock->Dominates(user->GetBlock())) {
  97       if (bound_type == nullptr) {
  98         bound_type = new (graph_->GetArena()) HBoundType(obj, ReferenceTypeInfo::CreateTop(false));
  99         notNullBlock->InsertInstructionBefore(bound_type, notNullBlock->GetFirstInstruction());
 100       }
 101       user->ReplaceInput(bound_type, it.Current()->GetIndex());
 102     }
 103   }
 104 }
 105
 106 // Detects if `block` is the True block for the pattern
 107 // `if (x instanceof ClassX) { }`
 108 // If that's the case insert an HBoundType instruction to bound the type of `x`
 109 // to `ClassX` in the scope of the dominated blocks.
 110 void ReferenceTypePropagation::BoundTypeForIfInstanceOf(HBasicBlock* block) {
 111   HIf* ifInstruction = block->GetLastInstruction()->AsIf();
 112   if (ifInstruction == nullptr) {
 113     return;
 114   }
 115   HInstruction* ifInput = ifInstruction->InputAt(0);
 116   HInstruction* instanceOf = nullptr;
 117   HBasicBlock* instanceOfTrueBlock = nullptr;
 118
 119   // The instruction simplifier has transformed:
 120   //   - `if (a instanceof A)` into an HIf with an HInstanceOf input
 121   //   - `if (!(a instanceof A)` into an HIf with an HBooleanNot input (which in turn
 122   //     has an HInstanceOf input)
 123   // So we should not see the usual HEqual here.
 124   if (ifInput->IsInstanceOf()) {
 125     instanceOf = ifInput;
 126     instanceOfTrueBlock = ifInstruction->IfTrueSuccessor();
 127   } else if (ifInput->IsBooleanNot() && ifInput->InputAt(0)->IsInstanceOf()) {
 128     instanceOf = ifInput->InputAt(0);
 129     instanceOfTrueBlock = ifInstruction->IfFalseSuccessor();
 130   } else {
 131     return;
 132   }
 133
 134   // We only need to bound the type if we have uses in the relevant block.
 135   // So start with null and create the HBoundType lazily, only if it's needed.
 136   HBoundType* bound_type = nullptr;
 137
 138   HInstruction* obj = instanceOf->InputAt(0);
 139   if (obj->GetReferenceTypeInfo().IsExact() && !obj->IsPhi()) {
 140     // This method is being called while doing a fixed-point calculation
 141     // over phis. Non-phis instruction whose type is already known do
 142     // not need to be bound to another type.
 143     // Not that this also prevents replacing `HLoadClass` with a `HBoundType`.
 144     // `HCheckCast` and `HInstanceOf` expect a `HLoadClass` as a second
 145     // input.
 146     return;
 147   }
 148   DCHECK(!obj->IsLoadClass()) << "We should not replace HLoadClass instructions";
 149   for (HUseIterator<HInstruction*> it(obj->GetUses()); !it.Done(); it.Advance()) {
 150     HInstruction* user = it.Current()->GetUser();
 151     if (instanceOfTrueBlock->Dominates(user->GetBlock())) {
 152       if (bound_type == nullptr) {
 153         HLoadClass* load_class = instanceOf->InputAt(1)->AsLoadClass();
 154
 155         ReferenceTypeInfo obj_rti = obj->GetReferenceTypeInfo();
 156         ReferenceTypeInfo class_rti = load_class->GetLoadedClassRTI();
 157         bound_type = new (graph_->GetArena()) HBoundType(obj, class_rti);
 158
 159         // Narrow the type as much as possible.
 160         {
 161           ScopedObjectAccess soa(Thread::Current());
 162           if (!load_class->IsResolved() || class_rti.IsSupertypeOf(obj_rti)) {
 163             bound_type->SetReferenceTypeInfo(obj_rti);
 164           } else {
 165             bound_type->SetReferenceTypeInfo(
 166                 ReferenceTypeInfo::Create(class_rti.GetTypeHandle(), /* is_exact */ false));
 167           }
 168         }
 169
 170         instanceOfTrueBlock->InsertInstructionBefore(
 171             bound_type, instanceOfTrueBlock->GetFirstInstruction());
 172       }
 173       user->ReplaceInput(bound_type, it.Current()->GetIndex());
 174     }
 175   }
 176 }
 177
 178 void ReferenceTypePropagation::VisitNewInstance(HNewInstance* instr) {
 179   ScopedObjectAccess soa(Thread::Current());
 180   mirror::DexCache* dex_cache = dex_compilation_unit_.GetClassLinker()->FindDexCache(dex_file_);
 181   // Get type from dex cache assuming it was populated by the verifier.
 182   mirror::Class* resolved_class = dex_cache->GetResolvedType(instr->GetTypeIndex());
 183   if (resolved_class != nullptr) {
 184     MutableHandle<mirror::Class> handle = handles_->NewHandle(resolved_class);
 185     instr->SetReferenceTypeInfo(ReferenceTypeInfo::Create(handle, true));
 186   }
 187 }
 188
 189 void ReferenceTypePropagation::VisitLoadClass(HLoadClass* instr) {
 190   ScopedObjectAccess soa(Thread::Current());
 191   mirror::DexCache* dex_cache = dex_compilation_unit_.GetClassLinker()->FindDexCache(dex_file_);
 192   // Get type from dex cache assuming it was populated by the verifier.
 193   mirror::Class* resolved_class = dex_cache->GetResolvedType(instr->GetTypeIndex());
 194   if (resolved_class != nullptr) {
 195     Handle<mirror::Class> handle = handles_->NewHandle(resolved_class);
 196     instr->SetLoadedClassRTI(ReferenceTypeInfo::Create(handle, /* is_exact */ true));
 197   }
 198   Handle<mirror::Class> class_handle = handles_->NewHandle(mirror::Class::GetJavaLangClass());
 199   instr->SetReferenceTypeInfo(ReferenceTypeInfo::Create(class_handle, /* is_exact */ true));
 200 }
 201
 202 void ReferenceTypePropagation::VisitPhi(HPhi* phi) {
 203   if (phi->GetType() != Primitive::kPrimNot) {
 204     return;
 205   }
 206
 207   if (phi->GetBlock()->IsLoopHeader()) {
 208     // Set the initial type for the phi. Use the non back edge input for reaching
 209     // a fixed point faster.
 210     AddToWorklist(phi);
 211     phi->SetCanBeNull(phi->InputAt(0)->CanBeNull());
 212     phi->SetReferenceTypeInfo(phi->InputAt(0)->GetReferenceTypeInfo());
 213   } else {
 214     // Eagerly compute the type of the phi, for quicker convergence. Note
 215     // that we don't need to add users to the worklist because we are
 216     // doing a reverse post-order visit, therefore either the phi users are
 217     // non-loop phi and will be visited later in the visit, or are loop-phis,
 218     // and they are already in the work list.
 219     UpdateNullability(phi);
 220     UpdateReferenceTypeInfo(phi);
 221   }
 222 }
 223
 224 ReferenceTypeInfo ReferenceTypePropagation::MergeTypes(const ReferenceTypeInfo& a,
 225                                                        const ReferenceTypeInfo& b) {
 226   bool is_exact = a.IsExact() && b.IsExact();
 227   bool is_top = a.IsTop() || b.IsTop();
 228   Handle<mirror::Class> type_handle;
 229
 230   if (!is_top) {
 231     if (a.GetTypeHandle().Get() == b.GetTypeHandle().Get()) {
 232       type_handle = a.GetTypeHandle();
 233     } else if (a.IsSupertypeOf(b)) {
 234       type_handle = a.GetTypeHandle();
 235       is_exact = false;
 236     } else if (b.IsSupertypeOf(a)) {
 237       type_handle = b.GetTypeHandle();
 238       is_exact = false;
 239     } else {
 240       // TODO: Find a common super class.
 241       is_top = true;
 242       is_exact = false;
 243     }
 244   }
 245
 246   return is_top
 247       ? ReferenceTypeInfo::CreateTop(is_exact)
 248       : ReferenceTypeInfo::Create(type_handle, is_exact);
 249 }
 250
 251 bool ReferenceTypePropagation::UpdateReferenceTypeInfo(HInstruction* instr) {
 252   ScopedObjectAccess soa(Thread::Current());
 253
 254   ReferenceTypeInfo previous_rti = instr->GetReferenceTypeInfo();
 255   if (instr->IsBoundType()) {
 256     UpdateBoundType(instr->AsBoundType());
 257   } else if (instr->IsPhi()) {
 258     UpdatePhi(instr->AsPhi());
 259   } else {
 260     LOG(FATAL) << "Invalid instruction (should not get here)";
 261   }
 262
 263   return !previous_rti.IsEqual(instr->GetReferenceTypeInfo());
 264 }
 265
 266 void ReferenceTypePropagation::UpdateBoundType(HBoundType* instr) {
 267   ReferenceTypeInfo new_rti = instr->InputAt(0)->GetReferenceTypeInfo();
 268   // Be sure that we don't go over the bounded type.
 269   ReferenceTypeInfo bound_rti = instr->GetBoundType();
 270   if (!bound_rti.IsSupertypeOf(new_rti)) {
 271     new_rti = bound_rti;
 272   }
 273   instr->SetReferenceTypeInfo(new_rti);
 274 }
 275
 276 void ReferenceTypePropagation::UpdatePhi(HPhi* instr) {
 277   ReferenceTypeInfo new_rti = instr->InputAt(0)->GetReferenceTypeInfo();
 278   if (new_rti.IsTop() && !new_rti.IsExact()) {
 279     // Early return if we are Top and inexact.
 280     instr->SetReferenceTypeInfo(new_rti);
 281     return;
 282   }
 283   for (size_t i = 1; i < instr->InputCount(); i++) {
 284     new_rti = MergeTypes(new_rti, instr->InputAt(i)->GetReferenceTypeInfo());
 285     if (new_rti.IsTop()) {
 286       if (!new_rti.IsExact()) {
 287         break;
 288       } else {
 289         continue;
 290       }
 291     }
 292   }
 293   instr->SetReferenceTypeInfo(new_rti);
 294 }
 295
 296 // Re-computes and updates the nullability of the instruction. Returns whether or
 297 // not the nullability was changed.
 298 bool ReferenceTypePropagation::UpdateNullability(HInstruction* instr) {
 299   DCHECK(instr->IsPhi() || instr->IsBoundType());
 300
 301   if (!instr->IsPhi()) {
 302     return false;
 303   }
 304
 305   HPhi* phi = instr->AsPhi();
 306   bool existing_can_be_null = phi->CanBeNull();
 307   bool new_can_be_null = false;
 308   for (size_t i = 0; i < phi->InputCount(); i++) {
 309     new_can_be_null |= phi->InputAt(i)->CanBeNull();
 310   }
 311   phi->SetCanBeNull(new_can_be_null);
 312
 313   return existing_can_be_null != new_can_be_null;
 314 }
 315
 316 void ReferenceTypePropagation::ProcessWorklist() {
 317   while (!worklist_.IsEmpty()) {
 318     HInstruction* instruction = worklist_.Pop();
 319     bool updated_nullability = UpdateNullability(instruction);
 320     bool updated_reference_type = UpdateReferenceTypeInfo(instruction);
 321     if (updated_nullability || updated_reference_type) {
 322       AddDependentInstructionsToWorklist(instruction);
 323     }
 324   }
 325 }
 326
 327 void ReferenceTypePropagation::AddToWorklist(HInstruction* instruction) {
 328   DCHECK_EQ(instruction->GetType(), Primitive::kPrimNot) << instruction->GetType();
 329   worklist_.Add(instruction);
 330 }
 331
 332 void ReferenceTypePropagation::AddDependentInstructionsToWorklist(HInstruction* instruction) {
 333   for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) {
 334     HInstruction* user = it.Current()->GetUser();
 335     if (user->IsPhi() || user->IsBoundType()) {
 336       AddToWorklist(user);
 337     }
 338   }
 339 }
 340 }  // namespace art