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