Home | History | Annotate | Download | only in optimizing 
      1 /*
      2  * Copyright (C) 2014 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 "prepare_for_register_allocation.h"
     18 
     19 namespace art {
     20 
     21 void PrepareForRegisterAllocation::Run() {
     22   // Order does not matter.
     23   for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) {
     24     HBasicBlock* block = it.Current();
     25     // No need to visit the phis.
     26     for (HInstructionIterator inst_it(block->GetInstructions()); !inst_it.Done();
     27          inst_it.Advance()) {
     28       inst_it.Current()->Accept(this);
     29     }
     30   }
     31 }
     32 
     33 void PrepareForRegisterAllocation::VisitNullCheck(HNullCheck* check) {
     34   check->ReplaceWith(check->InputAt(0));
     35 }
     36 
     37 void PrepareForRegisterAllocation::VisitDivZeroCheck(HDivZeroCheck* check) {
     38   check->ReplaceWith(check->InputAt(0));
     39 }
     40 
     41 void PrepareForRegisterAllocation::VisitBoundsCheck(HBoundsCheck* check) {
     42   check->ReplaceWith(check->InputAt(0));
     43 }
     44 
     45 void PrepareForRegisterAllocation::VisitBoundType(HBoundType* bound_type) {
     46   bound_type->ReplaceWith(bound_type->InputAt(0));
     47   bound_type->GetBlock()->RemoveInstruction(bound_type);
     48 }
     49 
     50 void PrepareForRegisterAllocation::VisitArraySet(HArraySet* instruction) {
     51   HInstruction* value = instruction->GetValue();
     52   // PrepareForRegisterAllocation::VisitBoundType may have replaced a
     53   // BoundType (as value input of this ArraySet) with a NullConstant.
     54   // If so, this ArraySet no longer needs a type check.
     55   if (value->IsNullConstant()) {
     56     DCHECK_EQ(value->GetType(), Primitive::kPrimNot);
     57     if (instruction->NeedsTypeCheck()) {
     58       instruction->ClearNeedsTypeCheck();
     59     }
     60   }
     61 }
     62 
     63 void PrepareForRegisterAllocation::VisitClinitCheck(HClinitCheck* check) {
     64   // Try to find a static invoke or a new-instance from which this check originated.
     65   HInstruction* implicit_clinit = nullptr;
     66   for (const HUseListNode<HInstruction*>& use : check->GetUses()) {
     67     HInstruction* user = use.GetUser();
     68     if ((user->IsInvokeStaticOrDirect() || user->IsNewInstance()) &&
     69         CanMoveClinitCheck(check, user)) {
     70       implicit_clinit = user;
     71       if (user->IsInvokeStaticOrDirect()) {
     72         DCHECK(user->AsInvokeStaticOrDirect()->IsStaticWithExplicitClinitCheck());
     73         user->AsInvokeStaticOrDirect()->RemoveExplicitClinitCheck(
     74             HInvokeStaticOrDirect::ClinitCheckRequirement::kImplicit);
     75       } else {
     76         DCHECK(user->IsNewInstance());
     77         // We delegate the initialization duty to the allocation.
     78         if (user->AsNewInstance()->GetEntrypoint() == kQuickAllocObjectInitialized) {
     79           user->AsNewInstance()->SetEntrypoint(kQuickAllocObjectResolved);
     80         }
     81       }
     82       break;
     83     }
     84   }
     85   // If we found a static invoke or new-instance for merging, remove the check
     86   // from dominated static invokes.
     87   if (implicit_clinit != nullptr) {
     88     const HUseList<HInstruction*>& uses = check->GetUses();
     89     for (auto it = uses.begin(), end = uses.end(); it != end; /* ++it below */) {
     90       HInstruction* user = it->GetUser();
     91       // All other uses must be dominated.
     92       DCHECK(implicit_clinit->StrictlyDominates(user) || (implicit_clinit == user));
     93       ++it;  // Advance before we remove the node, reference to the next node is preserved.
     94       if (user->IsInvokeStaticOrDirect()) {
     95         user->AsInvokeStaticOrDirect()->RemoveExplicitClinitCheck(
     96             HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
     97       }
     98     }
     99   }
    100 
    101   HLoadClass* load_class = check->GetLoadClass();
    102   bool can_merge_with_load_class = CanMoveClinitCheck(load_class, check);
    103 
    104   check->ReplaceWith(load_class);
    105 
    106   if (implicit_clinit != nullptr) {
    107     // Remove the check from the graph. It has been merged into the invoke or new-instance.
    108     check->GetBlock()->RemoveInstruction(check);
    109     // Check if we can merge the load class as well.
    110     if (can_merge_with_load_class && !load_class->HasUses()) {
    111       load_class->GetBlock()->RemoveInstruction(load_class);
    112     }
    113   } else if (can_merge_with_load_class && !load_class->NeedsAccessCheck()) {
    114     // Pass the initialization duty to the `HLoadClass` instruction,
    115     // and remove the instruction from the graph.
    116     load_class->SetMustGenerateClinitCheck(true);
    117     check->GetBlock()->RemoveInstruction(check);
    118   }
    119 }
    120 
    121 void PrepareForRegisterAllocation::VisitNewInstance(HNewInstance* instruction) {
    122   HLoadClass* load_class = instruction->InputAt(0)->AsLoadClass();
    123   bool has_only_one_use = load_class->HasOnlyOneNonEnvironmentUse();
    124   // Change the entrypoint to kQuickAllocObject if either:
    125   // - the class is finalizable (only kQuickAllocObject handles finalizable classes),
    126   // - the class needs access checks (we do not know if it's finalizable),
    127   // - or the load class has only one use.
    128   if (instruction->IsFinalizable() || has_only_one_use || load_class->NeedsAccessCheck()) {
    129     instruction->SetEntrypoint(kQuickAllocObject);
    130     instruction->ReplaceInput(GetGraph()->GetIntConstant(load_class->GetTypeIndex()), 0);
    131     // The allocation entry point that deals with access checks does not work with inlined
    132     // methods, so we need to check whether this allocation comes from an inlined method.
    133     // We also need to make the same check as for moving clinit check, whether the HLoadClass
    134     // has the clinit check responsibility or not (HLoadClass can throw anyway).
    135     if (has_only_one_use &&
    136         !instruction->GetEnvironment()->IsFromInlinedInvoke() &&
    137         CanMoveClinitCheck(load_class, instruction)) {
    138       // We can remove the load class from the graph. If it needed access checks, we delegate
    139       // the access check to the allocation.
    140       if (load_class->NeedsAccessCheck()) {
    141         instruction->SetEntrypoint(kQuickAllocObjectWithAccessCheck);
    142       }
    143       load_class->GetBlock()->RemoveInstruction(load_class);
    144     }
    145   }
    146 }
    147 
    148 bool PrepareForRegisterAllocation::CanEmitConditionAt(HCondition* condition,
    149                                                       HInstruction* user) const {
    150   if (condition->GetNext() != user) {
    151     return false;
    152   }
    153 
    154   if (user->IsIf() || user->IsDeoptimize()) {
    155     return true;
    156   }
    157 
    158   if (user->IsSelect() && user->AsSelect()->GetCondition() == condition) {
    159     return true;
    160   }
    161 
    162   return false;
    163 }
    164 
    165 void PrepareForRegisterAllocation::VisitCondition(HCondition* condition) {
    166   if (condition->HasOnlyOneNonEnvironmentUse()) {
    167     HInstruction* user = condition->GetUses().front().GetUser();
    168     if (CanEmitConditionAt(condition, user)) {
    169       condition->MarkEmittedAtUseSite();
    170     }
    171   }
    172 }
    173 
    174 void PrepareForRegisterAllocation::VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) {
    175   if (invoke->IsStaticWithExplicitClinitCheck()) {
    176     size_t last_input_index = invoke->InputCount() - 1;
    177     HLoadClass* last_input = invoke->InputAt(last_input_index)->AsLoadClass();
    178     DCHECK(last_input != nullptr)
    179         << "Last input is not HLoadClass. It is " << last_input->DebugName();
    180 
    181     // Detach the explicit class initialization check from the invoke.
    182     // Keeping track of the initializing instruction is no longer required
    183     // at this stage (i.e., after inlining has been performed).
    184     invoke->RemoveExplicitClinitCheck(HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
    185 
    186     // Merging with load class should have happened in VisitClinitCheck().
    187     DCHECK(!CanMoveClinitCheck(last_input, invoke));
    188   }
    189 }
    190 
    191 bool PrepareForRegisterAllocation::CanMoveClinitCheck(HInstruction* input,
    192                                                       HInstruction* user) const {
    193   // Determine if input and user come from the same dex instruction, so that we can move
    194   // the clinit check responsibility from one to the other, i.e. from HClinitCheck (user)
    195   // to HLoadClass (input), or from HClinitCheck (input) to HInvokeStaticOrDirect (user),
    196   // or from HLoadClass (input) to HNewInstance (user).
    197 
    198   // Start with a quick dex pc check.
    199   if (user->GetDexPc() != input->GetDexPc()) {
    200     return false;
    201   }
    202 
    203   // Now do a thorough environment check that this is really coming from the same instruction in
    204   // the same inlined graph. Unfortunately, we have to go through the whole environment chain.
    205   HEnvironment* user_environment = user->GetEnvironment();
    206   HEnvironment* input_environment = input->GetEnvironment();
    207   while (user_environment != nullptr || input_environment != nullptr) {
    208     if (user_environment == nullptr || input_environment == nullptr) {
    209       // Different environment chain length. This happens when a method is called
    210       // once directly and once indirectly through another inlined method.
    211       return false;
    212     }
    213     if (user_environment->GetDexPc() != input_environment->GetDexPc() ||
    214         user_environment->GetMethodIdx() != input_environment->GetMethodIdx() ||
    215         !IsSameDexFile(user_environment->GetDexFile(), input_environment->GetDexFile())) {
    216       return false;
    217     }
    218     user_environment = user_environment->GetParent();
    219     input_environment = input_environment->GetParent();
    220   }
    221 
    222   // Check for code motion taking the input to a different block.
    223   if (user->GetBlock() != input->GetBlock()) {
    224     return false;
    225   }
    226 
    227   // In debug mode, check that we have not inserted a throwing instruction
    228   // or an instruction with side effects between input and user.
    229   if (kIsDebugBuild) {
    230     for (HInstruction* between = input->GetNext(); between != user; between = between->GetNext()) {
    231       CHECK(between != nullptr);  // User must be after input in the same block.
    232       CHECK(!between->CanThrow());
    233       CHECK(!between->HasSideEffects());
    234     }
    235   }
    236   return true;
    237 }
    238 
    239 }  // namespace art
    240