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 "ssa_builder.h"
     18 
     19 #include "bytecode_utils.h"
     20 #include "nodes.h"
     21 #include "reference_type_propagation.h"
     22 #include "ssa_phi_elimination.h"
     23 
     24 namespace art {
     25 
     26 void SsaBuilder::FixNullConstantType() {
     27   // The order doesn't matter here.
     28   for (HReversePostOrderIterator itb(*graph_); !itb.Done(); itb.Advance()) {
     29     for (HInstructionIterator it(itb.Current()->GetInstructions()); !it.Done(); it.Advance()) {
     30       HInstruction* equality_instr = it.Current();
     31       if (!equality_instr->IsEqual() && !equality_instr->IsNotEqual()) {
     32         continue;
     33       }
     34       HInstruction* left = equality_instr->InputAt(0);
     35       HInstruction* right = equality_instr->InputAt(1);
     36       HInstruction* int_operand = nullptr;
     37 
     38       if ((left->GetType() == Primitive::kPrimNot) && (right->GetType() == Primitive::kPrimInt)) {
     39         int_operand = right;
     40       } else if ((right->GetType() == Primitive::kPrimNot)
     41                  && (left->GetType() == Primitive::kPrimInt)) {
     42         int_operand = left;
     43       } else {
     44         continue;
     45       }
     46 
     47       // If we got here, we are comparing against a reference and the int constant
     48       // should be replaced with a null constant.
     49       // Both type propagation and redundant phi elimination ensure `int_operand`
     50       // can only be the 0 constant.
     51       DCHECK(int_operand->IsIntConstant()) << int_operand->DebugName();
     52       DCHECK_EQ(0, int_operand->AsIntConstant()->GetValue());
     53       equality_instr->ReplaceInput(graph_->GetNullConstant(), int_operand == right ? 1 : 0);
     54     }
     55   }
     56 }
     57 
     58 void SsaBuilder::EquivalentPhisCleanup() {
     59   // The order doesn't matter here.
     60   for (HReversePostOrderIterator itb(*graph_); !itb.Done(); itb.Advance()) {
     61     for (HInstructionIterator it(itb.Current()->GetPhis()); !it.Done(); it.Advance()) {
     62       HPhi* phi = it.Current()->AsPhi();
     63       HPhi* next = phi->GetNextEquivalentPhiWithSameType();
     64       if (next != nullptr) {
     65         // Make sure we do not replace a live phi with a dead phi. A live phi
     66         // has been handled by the type propagation phase, unlike a dead phi.
     67         if (next->IsLive()) {
     68           phi->ReplaceWith(next);
     69           phi->SetDead();
     70         } else {
     71           next->ReplaceWith(phi);
     72         }
     73         DCHECK(next->GetNextEquivalentPhiWithSameType() == nullptr)
     74             << "More then one phi equivalent with type " << phi->GetType()
     75             << " found for phi" << phi->GetId();
     76       }
     77     }
     78   }
     79 }
     80 
     81 void SsaBuilder::FixEnvironmentPhis() {
     82   for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
     83     HBasicBlock* block = it.Current();
     84     for (HInstructionIterator it_phis(block->GetPhis()); !it_phis.Done(); it_phis.Advance()) {
     85       HPhi* phi = it_phis.Current()->AsPhi();
     86       // If the phi is not dead, or has no environment uses, there is nothing to do.
     87       if (!phi->IsDead() || !phi->HasEnvironmentUses()) continue;
     88       HInstruction* next = phi->GetNext();
     89       if (!phi->IsVRegEquivalentOf(next)) continue;
     90       if (next->AsPhi()->IsDead()) {
     91         // If the phi equivalent is dead, check if there is another one.
     92         next = next->GetNext();
     93         if (!phi->IsVRegEquivalentOf(next)) continue;
     94         // There can be at most two phi equivalents.
     95         DCHECK(!phi->IsVRegEquivalentOf(next->GetNext()));
     96         if (next->AsPhi()->IsDead()) continue;
     97       }
     98       // We found a live phi equivalent. Update the environment uses of `phi` with it.
     99       phi->ReplaceWith(next);
    100     }
    101   }
    102 }
    103 
    104 static void AddDependentInstructionsToWorklist(HInstruction* instruction,
    105                                                ArenaVector<HPhi*>* worklist) {
    106   // If `instruction` is a dead phi, type conflict was just identified. All its
    107   // live phi users, and transitively users of those users, therefore need to be
    108   // marked dead/conflicting too, so we add them to the worklist. Otherwise we
    109   // add users whose type does not match and needs to be updated.
    110   bool add_all_live_phis = instruction->IsPhi() && instruction->AsPhi()->IsDead();
    111   for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) {
    112     HInstruction* user = use.GetUser();
    113     if (user->IsPhi() && user->AsPhi()->IsLive()) {
    114       if (add_all_live_phis || user->GetType() != instruction->GetType()) {
    115         worklist->push_back(user->AsPhi());
    116       }
    117     }
    118   }
    119 }
    120 
    121 // Find a candidate primitive type for `phi` by merging the type of its inputs.
    122 // Return false if conflict is identified.
    123 static bool TypePhiFromInputs(HPhi* phi) {
    124   Primitive::Type common_type = phi->GetType();
    125 
    126   for (HInputIterator it(phi); !it.Done(); it.Advance()) {
    127     HInstruction* input = it.Current();
    128     if (input->IsPhi() && input->AsPhi()->IsDead()) {
    129       // Phis are constructed live so if an input is a dead phi, it must have
    130       // been made dead due to type conflict. Mark this phi conflicting too.
    131       return false;
    132     }
    133 
    134     Primitive::Type input_type = HPhi::ToPhiType(input->GetType());
    135     if (common_type == input_type) {
    136       // No change in type.
    137     } else if (Primitive::Is64BitType(common_type) != Primitive::Is64BitType(input_type)) {
    138       // Types are of different sizes, e.g. int vs. long. Must be a conflict.
    139       return false;
    140     } else if (Primitive::IsIntegralType(common_type)) {
    141       // Previous inputs were integral, this one is not but is of the same size.
    142       // This does not imply conflict since some bytecode instruction types are
    143       // ambiguous. TypeInputsOfPhi will either type them or detect a conflict.
    144       DCHECK(Primitive::IsFloatingPointType(input_type) || input_type == Primitive::kPrimNot);
    145       common_type = input_type;
    146     } else if (Primitive::IsIntegralType(input_type)) {
    147       // Input is integral, common type is not. Same as in the previous case, if
    148       // there is a conflict, it will be detected during TypeInputsOfPhi.
    149       DCHECK(Primitive::IsFloatingPointType(common_type) || common_type == Primitive::kPrimNot);
    150     } else {
    151       // Combining float and reference types. Clearly a conflict.
    152       DCHECK((common_type == Primitive::kPrimFloat && input_type == Primitive::kPrimNot) ||
    153              (common_type == Primitive::kPrimNot && input_type == Primitive::kPrimFloat));
    154       return false;
    155     }
    156   }
    157 
    158   // We have found a candidate type for the phi. Set it and return true. We may
    159   // still discover conflict whilst typing the individual inputs in TypeInputsOfPhi.
    160   phi->SetType(common_type);
    161   return true;
    162 }
    163 
    164 // Replace inputs of `phi` to match its type. Return false if conflict is identified.
    165 bool SsaBuilder::TypeInputsOfPhi(HPhi* phi, ArenaVector<HPhi*>* worklist) {
    166   Primitive::Type common_type = phi->GetType();
    167   if (common_type == Primitive::kPrimVoid || Primitive::IsIntegralType(common_type)) {
    168     // Phi either contains only other untyped phis (common_type == kPrimVoid),
    169     // or `common_type` is integral and we do not need to retype ambiguous inputs
    170     // because they are always constructed with the integral type candidate.
    171     if (kIsDebugBuild) {
    172       for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
    173         HInstruction* input = phi->InputAt(i);
    174         if (common_type == Primitive::kPrimVoid) {
    175           DCHECK(input->IsPhi() && input->GetType() == Primitive::kPrimVoid);
    176         } else {
    177           DCHECK((input->IsPhi() && input->GetType() == Primitive::kPrimVoid) ||
    178                  HPhi::ToPhiType(input->GetType()) == common_type);
    179         }
    180       }
    181     }
    182     // Inputs did not need to be replaced, hence no conflict. Report success.
    183     return true;
    184   } else {
    185     DCHECK(common_type == Primitive::kPrimNot || Primitive::IsFloatingPointType(common_type));
    186     for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
    187       HInstruction* input = phi->InputAt(i);
    188       if (input->GetType() != common_type) {
    189         // Input type does not match phi's type. Try to retype the input or
    190         // generate a suitably typed equivalent.
    191         HInstruction* equivalent = (common_type == Primitive::kPrimNot)
    192             ? GetReferenceTypeEquivalent(input)
    193             : GetFloatOrDoubleEquivalent(input, common_type);
    194         if (equivalent == nullptr) {
    195           // Input could not be typed. Report conflict.
    196           return false;
    197         }
    198         // Make sure the input did not change its type and we do not need to
    199         // update its users.
    200         DCHECK_NE(input, equivalent);
    201 
    202         phi->ReplaceInput(equivalent, i);
    203         if (equivalent->IsPhi()) {
    204           worklist->push_back(equivalent->AsPhi());
    205         }
    206       }
    207     }
    208     // All inputs either matched the type of the phi or we successfully replaced
    209     // them with a suitable equivalent. Report success.
    210     return true;
    211   }
    212 }
    213 
    214 // Attempt to set the primitive type of `phi` to match its inputs. Return whether
    215 // it was changed by the algorithm or not.
    216 bool SsaBuilder::UpdatePrimitiveType(HPhi* phi, ArenaVector<HPhi*>* worklist) {
    217   DCHECK(phi->IsLive());
    218   Primitive::Type original_type = phi->GetType();
    219 
    220   // Try to type the phi in two stages:
    221   // (1) find a candidate type for the phi by merging types of all its inputs,
    222   // (2) try to type the phi's inputs to that candidate type.
    223   // Either of these stages may detect a type conflict and fail, in which case
    224   // we immediately abort.
    225   if (!TypePhiFromInputs(phi) || !TypeInputsOfPhi(phi, worklist)) {
    226     // Conflict detected. Mark the phi dead and return true because it changed.
    227     phi->SetDead();
    228     return true;
    229   }
    230 
    231   // Return true if the type of the phi has changed.
    232   return phi->GetType() != original_type;
    233 }
    234 
    235 void SsaBuilder::RunPrimitiveTypePropagation() {
    236   ArenaVector<HPhi*> worklist(graph_->GetArena()->Adapter(kArenaAllocGraphBuilder));
    237 
    238   for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
    239     HBasicBlock* block = it.Current();
    240     if (block->IsLoopHeader()) {
    241       for (HInstructionIterator phi_it(block->GetPhis()); !phi_it.Done(); phi_it.Advance()) {
    242         HPhi* phi = phi_it.Current()->AsPhi();
    243         if (phi->IsLive()) {
    244           worklist.push_back(phi);
    245         }
    246       }
    247     } else {
    248       for (HInstructionIterator phi_it(block->GetPhis()); !phi_it.Done(); phi_it.Advance()) {
    249         // Eagerly compute the type of the phi, for quicker convergence. Note
    250         // that we don't need to add users to the worklist because we are
    251         // doing a reverse post-order visit, therefore either the phi users are
    252         // non-loop phi and will be visited later in the visit, or are loop-phis,
    253         // and they are already in the work list.
    254         HPhi* phi = phi_it.Current()->AsPhi();
    255         if (phi->IsLive()) {
    256           UpdatePrimitiveType(phi, &worklist);
    257         }
    258       }
    259     }
    260   }
    261 
    262   ProcessPrimitiveTypePropagationWorklist(&worklist);
    263   EquivalentPhisCleanup();
    264 }
    265 
    266 void SsaBuilder::ProcessPrimitiveTypePropagationWorklist(ArenaVector<HPhi*>* worklist) {
    267   // Process worklist
    268   while (!worklist->empty()) {
    269     HPhi* phi = worklist->back();
    270     worklist->pop_back();
    271     // The phi could have been made dead as a result of conflicts while in the
    272     // worklist. If it is now dead, there is no point in updating its type.
    273     if (phi->IsLive() && UpdatePrimitiveType(phi, worklist)) {
    274       AddDependentInstructionsToWorklist(phi, worklist);
    275     }
    276   }
    277 }
    278 
    279 static HArrayGet* FindFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget) {
    280   Primitive::Type type = aget->GetType();
    281   DCHECK(Primitive::IsIntOrLongType(type));
    282   HInstruction* next = aget->GetNext();
    283   if (next != nullptr && next->IsArrayGet()) {
    284     HArrayGet* next_aget = next->AsArrayGet();
    285     if (next_aget->IsEquivalentOf(aget)) {
    286       return next_aget;
    287     }
    288   }
    289   return nullptr;
    290 }
    291 
    292 static HArrayGet* CreateFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget) {
    293   Primitive::Type type = aget->GetType();
    294   DCHECK(Primitive::IsIntOrLongType(type));
    295   DCHECK(FindFloatOrDoubleEquivalentOfArrayGet(aget) == nullptr);
    296 
    297   HArrayGet* equivalent = new (aget->GetBlock()->GetGraph()->GetArena()) HArrayGet(
    298       aget->GetArray(),
    299       aget->GetIndex(),
    300       type == Primitive::kPrimInt ? Primitive::kPrimFloat : Primitive::kPrimDouble,
    301       aget->GetDexPc());
    302   aget->GetBlock()->InsertInstructionAfter(equivalent, aget);
    303   return equivalent;
    304 }
    305 
    306 static Primitive::Type GetPrimitiveArrayComponentType(HInstruction* array)
    307     SHARED_REQUIRES(Locks::mutator_lock_) {
    308   ReferenceTypeInfo array_type = array->GetReferenceTypeInfo();
    309   DCHECK(array_type.IsPrimitiveArrayClass());
    310   return array_type.GetTypeHandle()->GetComponentType()->GetPrimitiveType();
    311 }
    312 
    313 bool SsaBuilder::FixAmbiguousArrayOps() {
    314   if (ambiguous_agets_.empty() && ambiguous_asets_.empty()) {
    315     return true;
    316   }
    317 
    318   // The wrong ArrayGet equivalent may still have Phi uses coming from ArraySet
    319   // uses (because they are untyped) and environment uses (if --debuggable).
    320   // After resolving all ambiguous ArrayGets, we will re-run primitive type
    321   // propagation on the Phis which need to be updated.
    322   ArenaVector<HPhi*> worklist(graph_->GetArena()->Adapter(kArenaAllocGraphBuilder));
    323 
    324   {
    325     ScopedObjectAccess soa(Thread::Current());
    326 
    327     for (HArrayGet* aget_int : ambiguous_agets_) {
    328       HInstruction* array = aget_int->GetArray();
    329       if (!array->GetReferenceTypeInfo().IsPrimitiveArrayClass()) {
    330         // RTP did not type the input array. Bail.
    331         return false;
    332       }
    333 
    334       HArrayGet* aget_float = FindFloatOrDoubleEquivalentOfArrayGet(aget_int);
    335       Primitive::Type array_type = GetPrimitiveArrayComponentType(array);
    336       DCHECK_EQ(Primitive::Is64BitType(aget_int->GetType()), Primitive::Is64BitType(array_type));
    337 
    338       if (Primitive::IsIntOrLongType(array_type)) {
    339         if (aget_float != nullptr) {
    340           // There is a float/double equivalent. We must replace it and re-run
    341           // primitive type propagation on all dependent instructions.
    342           aget_float->ReplaceWith(aget_int);
    343           aget_float->GetBlock()->RemoveInstruction(aget_float);
    344           AddDependentInstructionsToWorklist(aget_int, &worklist);
    345         }
    346       } else {
    347         DCHECK(Primitive::IsFloatingPointType(array_type));
    348         if (aget_float == nullptr) {
    349           // This is a float/double ArrayGet but there were no typed uses which
    350           // would create the typed equivalent. Create it now.
    351           aget_float = CreateFloatOrDoubleEquivalentOfArrayGet(aget_int);
    352         }
    353         // Replace the original int/long instruction. Note that it may have phi
    354         // uses, environment uses, as well as real uses (from untyped ArraySets).
    355         // We need to re-run primitive type propagation on its dependent instructions.
    356         aget_int->ReplaceWith(aget_float);
    357         aget_int->GetBlock()->RemoveInstruction(aget_int);
    358         AddDependentInstructionsToWorklist(aget_float, &worklist);
    359       }
    360     }
    361 
    362     // Set a flag stating that types of ArrayGets have been resolved. Requesting
    363     // equivalent of the wrong type with GetFloatOrDoubleEquivalentOfArrayGet
    364     // will fail from now on.
    365     agets_fixed_ = true;
    366 
    367     for (HArraySet* aset : ambiguous_asets_) {
    368       HInstruction* array = aset->GetArray();
    369       if (!array->GetReferenceTypeInfo().IsPrimitiveArrayClass()) {
    370         // RTP did not type the input array. Bail.
    371         return false;
    372       }
    373 
    374       HInstruction* value = aset->GetValue();
    375       Primitive::Type value_type = value->GetType();
    376       Primitive::Type array_type = GetPrimitiveArrayComponentType(array);
    377       DCHECK_EQ(Primitive::Is64BitType(value_type), Primitive::Is64BitType(array_type));
    378 
    379       if (Primitive::IsFloatingPointType(array_type)) {
    380         if (!Primitive::IsFloatingPointType(value_type)) {
    381           DCHECK(Primitive::IsIntegralType(value_type));
    382           // Array elements are floating-point but the value has not been replaced
    383           // with its floating-point equivalent. The replacement must always
    384           // succeed in code validated by the verifier.
    385           HInstruction* equivalent = GetFloatOrDoubleEquivalent(value, array_type);
    386           DCHECK(equivalent != nullptr);
    387           aset->ReplaceInput(equivalent, /* input_index */ 2);
    388           if (equivalent->IsPhi()) {
    389             // Returned equivalent is a phi which may not have had its inputs
    390             // replaced yet. We need to run primitive type propagation on it.
    391             worklist.push_back(equivalent->AsPhi());
    392           }
    393         }
    394       } else {
    395         // Array elements are integral and the value assigned to it initially
    396         // was integral too. Nothing to do.
    397         DCHECK(Primitive::IsIntegralType(array_type));
    398         DCHECK(Primitive::IsIntegralType(value_type));
    399       }
    400     }
    401   }
    402 
    403   if (!worklist.empty()) {
    404     ProcessPrimitiveTypePropagationWorklist(&worklist);
    405     EquivalentPhisCleanup();
    406   }
    407 
    408   return true;
    409 }
    410 
    411 static bool HasAliasInEnvironments(HInstruction* instruction) {
    412   HEnvironment* last_user = nullptr;
    413   for (const HUseListNode<HEnvironment*>& use : instruction->GetEnvUses()) {
    414     DCHECK(use.GetUser() != nullptr);
    415     // Note: The first comparison (== null) always fails.
    416     if (use.GetUser() == last_user) {
    417       return true;
    418     }
    419     last_user = use.GetUser();
    420   }
    421 
    422   if (kIsDebugBuild) {
    423     // Do a quadratic search to ensure same environment uses are next
    424     // to each other.
    425     const HUseList<HEnvironment*>& env_uses = instruction->GetEnvUses();
    426     for (auto current = env_uses.begin(), end = env_uses.end(); current != end; ++current) {
    427       auto next = current;
    428       for (++next; next != end; ++next) {
    429         DCHECK(next->GetUser() != current->GetUser());
    430       }
    431     }
    432   }
    433   return false;
    434 }
    435 
    436 void SsaBuilder::RemoveRedundantUninitializedStrings() {
    437   if (graph_->IsDebuggable()) {
    438     // Do not perform the optimization for consistency with the interpreter
    439     // which always allocates an object for new-instance of String.
    440     return;
    441   }
    442 
    443   for (HNewInstance* new_instance : uninitialized_strings_) {
    444     DCHECK(new_instance->IsInBlock());
    445     DCHECK(new_instance->IsStringAlloc());
    446 
    447     // Replace NewInstance of String with NullConstant if not used prior to
    448     // calling StringFactory. In case of deoptimization, the interpreter is
    449     // expected to skip null check on the `this` argument of the StringFactory call.
    450     if (!new_instance->HasNonEnvironmentUses() && !HasAliasInEnvironments(new_instance)) {
    451       new_instance->ReplaceWith(graph_->GetNullConstant());
    452       new_instance->GetBlock()->RemoveInstruction(new_instance);
    453 
    454       // Remove LoadClass if not needed any more.
    455       HInstruction* input = new_instance->InputAt(0);
    456       HLoadClass* load_class = nullptr;
    457 
    458       // If the class was not present in the dex cache at the point of building
    459       // the graph, the builder inserted a HClinitCheck in between. Since the String
    460       // class is always initialized at the point of running Java code, we can remove
    461       // that check.
    462       if (input->IsClinitCheck()) {
    463         load_class = input->InputAt(0)->AsLoadClass();
    464         input->ReplaceWith(load_class);
    465         input->GetBlock()->RemoveInstruction(input);
    466       } else {
    467         load_class = input->AsLoadClass();
    468         DCHECK(new_instance->IsStringAlloc());
    469         DCHECK(!load_class->NeedsAccessCheck()) << "String class is always accessible";
    470       }
    471       DCHECK(load_class != nullptr);
    472       if (!load_class->HasUses()) {
    473         // Even if the HLoadClass needs access check, we can remove it, as we know the
    474         // String class does not need it.
    475         load_class->GetBlock()->RemoveInstruction(load_class);
    476       }
    477     }
    478   }
    479 }
    480 
    481 GraphAnalysisResult SsaBuilder::BuildSsa() {
    482   DCHECK(!graph_->IsInSsaForm());
    483 
    484   // 1) Propagate types of phis. At this point, phis are typed void in the general
    485   // case, or float/double/reference if we created an equivalent phi. So we need
    486   // to propagate the types across phis to give them a correct type. If a type
    487   // conflict is detected in this stage, the phi is marked dead.
    488   RunPrimitiveTypePropagation();
    489 
    490   // 2) Now that the correct primitive types have been assigned, we can get rid
    491   // of redundant phis. Note that we cannot do this phase before type propagation,
    492   // otherwise we could get rid of phi equivalents, whose presence is a requirement
    493   // for the type propagation phase. Note that this is to satisfy statement (a)
    494   // of the SsaBuilder (see ssa_builder.h).
    495   SsaRedundantPhiElimination(graph_).Run();
    496 
    497   // 3) Fix the type for null constants which are part of an equality comparison.
    498   // We need to do this after redundant phi elimination, to ensure the only cases
    499   // that we can see are reference comparison against 0. The redundant phi
    500   // elimination ensures we do not see a phi taking two 0 constants in a HEqual
    501   // or HNotEqual.
    502   FixNullConstantType();
    503 
    504   // 4) Compute type of reference type instructions. The pass assumes that
    505   // NullConstant has been fixed up.
    506   ReferenceTypePropagation(graph_, dex_cache_, handles_, /* is_first_run */ true).Run();
    507 
    508   // 5) HInstructionBuilder duplicated ArrayGet instructions with ambiguous type
    509   // (int/float or long/double) and marked ArraySets with ambiguous input type.
    510   // Now that RTP computed the type of the array input, the ambiguity can be
    511   // resolved and the correct equivalents kept.
    512   if (!FixAmbiguousArrayOps()) {
    513     return kAnalysisFailAmbiguousArrayOp;
    514   }
    515 
    516   // 6) Mark dead phis. This will mark phis which are not used by instructions
    517   // or other live phis. If compiling as debuggable code, phis will also be kept
    518   // live if they have an environment use.
    519   SsaDeadPhiElimination dead_phi_elimimation(graph_);
    520   dead_phi_elimimation.MarkDeadPhis();
    521 
    522   // 7) Make sure environments use the right phi equivalent: a phi marked dead
    523   // can have a phi equivalent that is not dead. In that case we have to replace
    524   // it with the live equivalent because deoptimization and try/catch rely on
    525   // environments containing values of all live vregs at that point. Note that
    526   // there can be multiple phis for the same Dex register that are live
    527   // (for example when merging constants), in which case it is okay for the
    528   // environments to just reference one.
    529   FixEnvironmentPhis();
    530 
    531   // 8) Now that the right phis are used for the environments, we can eliminate
    532   // phis we do not need. Regardless of the debuggable status, this phase is
    533   /// necessary for statement (b) of the SsaBuilder (see ssa_builder.h), as well
    534   // as for the code generation, which does not deal with phis of conflicting
    535   // input types.
    536   dead_phi_elimimation.EliminateDeadPhis();
    537 
    538   // 9) HInstructionBuidler replaced uses of NewInstances of String with the
    539   // results of their corresponding StringFactory calls. Unless the String
    540   // objects are used before they are initialized, they can be replaced with
    541   // NullConstant. Note that this optimization is valid only if unsimplified
    542   // code does not use the uninitialized value because we assume execution can
    543   // be deoptimized at any safepoint. We must therefore perform it before any
    544   // other optimizations.
    545   RemoveRedundantUninitializedStrings();
    546 
    547   graph_->SetInSsaForm();
    548   return kAnalysisSuccess;
    549 }
    550 
    551 /**
    552  * Constants in the Dex format are not typed. So the builder types them as
    553  * integers, but when doing the SSA form, we might realize the constant
    554  * is used for floating point operations. We create a floating-point equivalent
    555  * constant to make the operations correctly typed.
    556  */
    557 HFloatConstant* SsaBuilder::GetFloatEquivalent(HIntConstant* constant) {
    558   // We place the floating point constant next to this constant.
    559   HFloatConstant* result = constant->GetNext()->AsFloatConstant();
    560   if (result == nullptr) {
    561     float value = bit_cast<float, int32_t>(constant->GetValue());
    562     result = new (graph_->GetArena()) HFloatConstant(value);
    563     constant->GetBlock()->InsertInstructionBefore(result, constant->GetNext());
    564     graph_->CacheFloatConstant(result);
    565   } else {
    566     // If there is already a constant with the expected type, we know it is
    567     // the floating point equivalent of this constant.
    568     DCHECK_EQ((bit_cast<int32_t, float>(result->GetValue())), constant->GetValue());
    569   }
    570   return result;
    571 }
    572 
    573 /**
    574  * Wide constants in the Dex format are not typed. So the builder types them as
    575  * longs, but when doing the SSA form, we might realize the constant
    576  * is used for floating point operations. We create a floating-point equivalent
    577  * constant to make the operations correctly typed.
    578  */
    579 HDoubleConstant* SsaBuilder::GetDoubleEquivalent(HLongConstant* constant) {
    580   // We place the floating point constant next to this constant.
    581   HDoubleConstant* result = constant->GetNext()->AsDoubleConstant();
    582   if (result == nullptr) {
    583     double value = bit_cast<double, int64_t>(constant->GetValue());
    584     result = new (graph_->GetArena()) HDoubleConstant(value);
    585     constant->GetBlock()->InsertInstructionBefore(result, constant->GetNext());
    586     graph_->CacheDoubleConstant(result);
    587   } else {
    588     // If there is already a constant with the expected type, we know it is
    589     // the floating point equivalent of this constant.
    590     DCHECK_EQ((bit_cast<int64_t, double>(result->GetValue())), constant->GetValue());
    591   }
    592   return result;
    593 }
    594 
    595 /**
    596  * Because of Dex format, we might end up having the same phi being
    597  * used for non floating point operations and floating point / reference operations.
    598  * Because we want the graph to be correctly typed (and thereafter avoid moves between
    599  * floating point registers and core registers), we need to create a copy of the
    600  * phi with a floating point / reference type.
    601  */
    602 HPhi* SsaBuilder::GetFloatDoubleOrReferenceEquivalentOfPhi(HPhi* phi, Primitive::Type type) {
    603   DCHECK(phi->IsLive()) << "Cannot get equivalent of a dead phi since it would create a live one.";
    604 
    605   // We place the floating point /reference phi next to this phi.
    606   HInstruction* next = phi->GetNext();
    607   if (next != nullptr
    608       && next->AsPhi()->GetRegNumber() == phi->GetRegNumber()
    609       && next->GetType() != type) {
    610     // Move to the next phi to see if it is the one we are looking for.
    611     next = next->GetNext();
    612   }
    613 
    614   if (next == nullptr
    615       || (next->AsPhi()->GetRegNumber() != phi->GetRegNumber())
    616       || (next->GetType() != type)) {
    617     ArenaAllocator* allocator = graph_->GetArena();
    618     HPhi* new_phi = new (allocator) HPhi(allocator, phi->GetRegNumber(), phi->InputCount(), type);
    619     for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
    620       // Copy the inputs. Note that the graph may not be correctly typed
    621       // by doing this copy, but the type propagation phase will fix it.
    622       new_phi->SetRawInputAt(i, phi->InputAt(i));
    623     }
    624     phi->GetBlock()->InsertPhiAfter(new_phi, phi);
    625     DCHECK(new_phi->IsLive());
    626     return new_phi;
    627   } else {
    628     // An existing equivalent was found. If it is dead, conflict was previously
    629     // identified and we return nullptr instead.
    630     HPhi* next_phi = next->AsPhi();
    631     DCHECK_EQ(next_phi->GetType(), type);
    632     return next_phi->IsLive() ? next_phi : nullptr;
    633   }
    634 }
    635 
    636 HArrayGet* SsaBuilder::GetFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget) {
    637   DCHECK(Primitive::IsIntegralType(aget->GetType()));
    638 
    639   if (!Primitive::IsIntOrLongType(aget->GetType())) {
    640     // Cannot type boolean, char, byte, short to float/double.
    641     return nullptr;
    642   }
    643 
    644   DCHECK(ContainsElement(ambiguous_agets_, aget));
    645   if (agets_fixed_) {
    646     // This used to be an ambiguous ArrayGet but its type has been resolved to
    647     // int/long. Requesting a float/double equivalent should lead to a conflict.
    648     if (kIsDebugBuild) {
    649       ScopedObjectAccess soa(Thread::Current());
    650       DCHECK(Primitive::IsIntOrLongType(GetPrimitiveArrayComponentType(aget->GetArray())));
    651     }
    652     return nullptr;
    653   } else {
    654     // This is an ambiguous ArrayGet which has not been resolved yet. Return an
    655     // equivalent float/double instruction to use until it is resolved.
    656     HArrayGet* equivalent = FindFloatOrDoubleEquivalentOfArrayGet(aget);
    657     return (equivalent == nullptr) ? CreateFloatOrDoubleEquivalentOfArrayGet(aget) : equivalent;
    658   }
    659 }
    660 
    661 HInstruction* SsaBuilder::GetFloatOrDoubleEquivalent(HInstruction* value, Primitive::Type type) {
    662   if (value->IsArrayGet()) {
    663     return GetFloatOrDoubleEquivalentOfArrayGet(value->AsArrayGet());
    664   } else if (value->IsLongConstant()) {
    665     return GetDoubleEquivalent(value->AsLongConstant());
    666   } else if (value->IsIntConstant()) {
    667     return GetFloatEquivalent(value->AsIntConstant());
    668   } else if (value->IsPhi()) {
    669     return GetFloatDoubleOrReferenceEquivalentOfPhi(value->AsPhi(), type);
    670   } else {
    671     return nullptr;
    672   }
    673 }
    674 
    675 HInstruction* SsaBuilder::GetReferenceTypeEquivalent(HInstruction* value) {
    676   if (value->IsIntConstant() && value->AsIntConstant()->GetValue() == 0) {
    677     return graph_->GetNullConstant();
    678   } else if (value->IsPhi()) {
    679     return GetFloatDoubleOrReferenceEquivalentOfPhi(value->AsPhi(), Primitive::kPrimNot);
    680   } else {
    681     return nullptr;
    682   }
    683 }
    684 
    685 }  // namespace art
    686