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