ssa_builder.cc revision bfb80d25eaeb7a604d5dd25a370e3869e96a33ab
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 "mirror/class-inl.h" 21#include "nodes.h" 22#include "reference_type_propagation.h" 23#include "scoped_thread_state_change-inl.h" 24#include "ssa_phi_elimination.h" 25 26namespace art { 27 28void SsaBuilder::FixNullConstantType() { 29 // The order doesn't matter here. 30 for (HBasicBlock* block : graph_->GetReversePostOrder()) { 31 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 32 HInstruction* equality_instr = it.Current(); 33 if (!equality_instr->IsEqual() && !equality_instr->IsNotEqual()) { 34 continue; 35 } 36 HInstruction* left = equality_instr->InputAt(0); 37 HInstruction* right = equality_instr->InputAt(1); 38 HInstruction* int_operand = nullptr; 39 40 if ((left->GetType() == Primitive::kPrimNot) && (right->GetType() == Primitive::kPrimInt)) { 41 int_operand = right; 42 } else if ((right->GetType() == Primitive::kPrimNot) 43 && (left->GetType() == Primitive::kPrimInt)) { 44 int_operand = left; 45 } else { 46 continue; 47 } 48 49 // If we got here, we are comparing against a reference and the int constant 50 // should be replaced with a null constant. 51 // Both type propagation and redundant phi elimination ensure `int_operand` 52 // can only be the 0 constant. 53 DCHECK(int_operand->IsIntConstant()) << int_operand->DebugName(); 54 DCHECK_EQ(0, int_operand->AsIntConstant()->GetValue()); 55 equality_instr->ReplaceInput(graph_->GetNullConstant(), int_operand == right ? 1 : 0); 56 } 57 } 58} 59 60void SsaBuilder::EquivalentPhisCleanup() { 61 // The order doesn't matter here. 62 for (HBasicBlock* block : graph_->GetReversePostOrder()) { 63 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 64 HPhi* phi = it.Current()->AsPhi(); 65 HPhi* next = phi->GetNextEquivalentPhiWithSameType(); 66 if (next != nullptr) { 67 // Make sure we do not replace a live phi with a dead phi. A live phi 68 // has been handled by the type propagation phase, unlike a dead phi. 69 if (next->IsLive()) { 70 phi->ReplaceWith(next); 71 phi->SetDead(); 72 } else { 73 next->ReplaceWith(phi); 74 } 75 DCHECK(next->GetNextEquivalentPhiWithSameType() == nullptr) 76 << "More then one phi equivalent with type " << phi->GetType() 77 << " found for phi" << phi->GetId(); 78 } 79 } 80 } 81} 82 83void SsaBuilder::FixEnvironmentPhis() { 84 for (HBasicBlock* block : graph_->GetReversePostOrder()) { 85 for (HInstructionIterator it_phis(block->GetPhis()); !it_phis.Done(); it_phis.Advance()) { 86 HPhi* phi = it_phis.Current()->AsPhi(); 87 // If the phi is not dead, or has no environment uses, there is nothing to do. 88 if (!phi->IsDead() || !phi->HasEnvironmentUses()) continue; 89 HInstruction* next = phi->GetNext(); 90 if (!phi->IsVRegEquivalentOf(next)) continue; 91 if (next->AsPhi()->IsDead()) { 92 // If the phi equivalent is dead, check if there is another one. 93 next = next->GetNext(); 94 if (!phi->IsVRegEquivalentOf(next)) continue; 95 // There can be at most two phi equivalents. 96 DCHECK(!phi->IsVRegEquivalentOf(next->GetNext())); 97 if (next->AsPhi()->IsDead()) continue; 98 } 99 // We found a live phi equivalent. Update the environment uses of `phi` with it. 100 phi->ReplaceWith(next); 101 } 102 } 103} 104 105static void AddDependentInstructionsToWorklist(HInstruction* instruction, 106 ArenaVector<HPhi*>* worklist) { 107 // If `instruction` is a dead phi, type conflict was just identified. All its 108 // live phi users, and transitively users of those users, therefore need to be 109 // marked dead/conflicting too, so we add them to the worklist. Otherwise we 110 // add users whose type does not match and needs to be updated. 111 bool add_all_live_phis = instruction->IsPhi() && instruction->AsPhi()->IsDead(); 112 for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) { 113 HInstruction* user = use.GetUser(); 114 if (user->IsPhi() && user->AsPhi()->IsLive()) { 115 if (add_all_live_phis || user->GetType() != instruction->GetType()) { 116 worklist->push_back(user->AsPhi()); 117 } 118 } 119 } 120} 121 122// Find a candidate primitive type for `phi` by merging the type of its inputs. 123// Return false if conflict is identified. 124static bool TypePhiFromInputs(HPhi* phi) { 125 Primitive::Type common_type = phi->GetType(); 126 127 for (HInstruction* input : phi->GetInputs()) { 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. 165bool SsaBuilder::TypeInputsOfPhi(HPhi* phi, ArenaVector<HPhi*>* worklist) { 166 Primitive::Type common_type = phi->GetType(); 167 if (Primitive::IsIntegralType(common_type)) { 168 // We do not need to retype ambiguous inputs because they are always constructed 169 // with the integral type candidate. 170 if (kIsDebugBuild) { 171 for (HInstruction* input : phi->GetInputs()) { 172 DCHECK(HPhi::ToPhiType(input->GetType()) == common_type); 173 } 174 } 175 // Inputs did not need to be replaced, hence no conflict. Report success. 176 return true; 177 } else { 178 DCHECK(common_type == Primitive::kPrimNot || Primitive::IsFloatingPointType(common_type)); 179 HInputsRef inputs = phi->GetInputs(); 180 for (size_t i = 0; i < inputs.size(); ++i) { 181 HInstruction* input = inputs[i]; 182 if (input->GetType() != common_type) { 183 // Input type does not match phi's type. Try to retype the input or 184 // generate a suitably typed equivalent. 185 HInstruction* equivalent = (common_type == Primitive::kPrimNot) 186 ? GetReferenceTypeEquivalent(input) 187 : GetFloatOrDoubleEquivalent(input, common_type); 188 if (equivalent == nullptr) { 189 // Input could not be typed. Report conflict. 190 return false; 191 } 192 // Make sure the input did not change its type and we do not need to 193 // update its users. 194 DCHECK_NE(input, equivalent); 195 196 phi->ReplaceInput(equivalent, i); 197 if (equivalent->IsPhi()) { 198 worklist->push_back(equivalent->AsPhi()); 199 } 200 } 201 } 202 // All inputs either matched the type of the phi or we successfully replaced 203 // them with a suitable equivalent. Report success. 204 return true; 205 } 206} 207 208// Attempt to set the primitive type of `phi` to match its inputs. Return whether 209// it was changed by the algorithm or not. 210bool SsaBuilder::UpdatePrimitiveType(HPhi* phi, ArenaVector<HPhi*>* worklist) { 211 DCHECK(phi->IsLive()); 212 Primitive::Type original_type = phi->GetType(); 213 214 // Try to type the phi in two stages: 215 // (1) find a candidate type for the phi by merging types of all its inputs, 216 // (2) try to type the phi's inputs to that candidate type. 217 // Either of these stages may detect a type conflict and fail, in which case 218 // we immediately abort. 219 if (!TypePhiFromInputs(phi) || !TypeInputsOfPhi(phi, worklist)) { 220 // Conflict detected. Mark the phi dead and return true because it changed. 221 phi->SetDead(); 222 return true; 223 } 224 225 // Return true if the type of the phi has changed. 226 return phi->GetType() != original_type; 227} 228 229void SsaBuilder::RunPrimitiveTypePropagation() { 230 ArenaVector<HPhi*> worklist(graph_->GetArena()->Adapter(kArenaAllocGraphBuilder)); 231 232 for (HBasicBlock* block : graph_->GetReversePostOrder()) { 233 if (block->IsLoopHeader()) { 234 for (HInstructionIterator phi_it(block->GetPhis()); !phi_it.Done(); phi_it.Advance()) { 235 HPhi* phi = phi_it.Current()->AsPhi(); 236 if (phi->IsLive()) { 237 worklist.push_back(phi); 238 } 239 } 240 } else { 241 for (HInstructionIterator phi_it(block->GetPhis()); !phi_it.Done(); phi_it.Advance()) { 242 // Eagerly compute the type of the phi, for quicker convergence. Note 243 // that we don't need to add users to the worklist because we are 244 // doing a reverse post-order visit, therefore either the phi users are 245 // non-loop phi and will be visited later in the visit, or are loop-phis, 246 // and they are already in the work list. 247 HPhi* phi = phi_it.Current()->AsPhi(); 248 if (phi->IsLive()) { 249 UpdatePrimitiveType(phi, &worklist); 250 } 251 } 252 } 253 } 254 255 ProcessPrimitiveTypePropagationWorklist(&worklist); 256 EquivalentPhisCleanup(); 257} 258 259void SsaBuilder::ProcessPrimitiveTypePropagationWorklist(ArenaVector<HPhi*>* worklist) { 260 // Process worklist 261 while (!worklist->empty()) { 262 HPhi* phi = worklist->back(); 263 worklist->pop_back(); 264 // The phi could have been made dead as a result of conflicts while in the 265 // worklist. If it is now dead, there is no point in updating its type. 266 if (phi->IsLive() && UpdatePrimitiveType(phi, worklist)) { 267 AddDependentInstructionsToWorklist(phi, worklist); 268 } 269 } 270} 271 272static HArrayGet* FindFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget) { 273 Primitive::Type type = aget->GetType(); 274 DCHECK(Primitive::IsIntOrLongType(type)); 275 HInstruction* next = aget->GetNext(); 276 if (next != nullptr && next->IsArrayGet()) { 277 HArrayGet* next_aget = next->AsArrayGet(); 278 if (next_aget->IsEquivalentOf(aget)) { 279 return next_aget; 280 } 281 } 282 return nullptr; 283} 284 285static HArrayGet* CreateFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget) { 286 Primitive::Type type = aget->GetType(); 287 DCHECK(Primitive::IsIntOrLongType(type)); 288 DCHECK(FindFloatOrDoubleEquivalentOfArrayGet(aget) == nullptr); 289 290 HArrayGet* equivalent = new (aget->GetBlock()->GetGraph()->GetArena()) HArrayGet( 291 aget->GetArray(), 292 aget->GetIndex(), 293 type == Primitive::kPrimInt ? Primitive::kPrimFloat : Primitive::kPrimDouble, 294 aget->GetDexPc()); 295 aget->GetBlock()->InsertInstructionAfter(equivalent, aget); 296 return equivalent; 297} 298 299static Primitive::Type GetPrimitiveArrayComponentType(HInstruction* array) 300 REQUIRES_SHARED(Locks::mutator_lock_) { 301 ReferenceTypeInfo array_type = array->GetReferenceTypeInfo(); 302 DCHECK(array_type.IsPrimitiveArrayClass()); 303 return array_type.GetTypeHandle()->GetComponentType()->GetPrimitiveType(); 304} 305 306bool SsaBuilder::FixAmbiguousArrayOps() { 307 if (ambiguous_agets_.empty() && ambiguous_asets_.empty()) { 308 return true; 309 } 310 311 // The wrong ArrayGet equivalent may still have Phi uses coming from ArraySet 312 // uses (because they are untyped) and environment uses (if --debuggable). 313 // After resolving all ambiguous ArrayGets, we will re-run primitive type 314 // propagation on the Phis which need to be updated. 315 ArenaVector<HPhi*> worklist(graph_->GetArena()->Adapter(kArenaAllocGraphBuilder)); 316 317 { 318 ScopedObjectAccess soa(Thread::Current()); 319 320 for (HArrayGet* aget_int : ambiguous_agets_) { 321 HInstruction* array = aget_int->GetArray(); 322 if (!array->GetReferenceTypeInfo().IsPrimitiveArrayClass()) { 323 // RTP did not type the input array. Bail. 324 return false; 325 } 326 327 HArrayGet* aget_float = FindFloatOrDoubleEquivalentOfArrayGet(aget_int); 328 Primitive::Type array_type = GetPrimitiveArrayComponentType(array); 329 DCHECK_EQ(Primitive::Is64BitType(aget_int->GetType()), Primitive::Is64BitType(array_type)); 330 331 if (Primitive::IsIntOrLongType(array_type)) { 332 if (aget_float != nullptr) { 333 // There is a float/double equivalent. We must replace it and re-run 334 // primitive type propagation on all dependent instructions. 335 aget_float->ReplaceWith(aget_int); 336 aget_float->GetBlock()->RemoveInstruction(aget_float); 337 AddDependentInstructionsToWorklist(aget_int, &worklist); 338 } 339 } else { 340 DCHECK(Primitive::IsFloatingPointType(array_type)); 341 if (aget_float == nullptr) { 342 // This is a float/double ArrayGet but there were no typed uses which 343 // would create the typed equivalent. Create it now. 344 aget_float = CreateFloatOrDoubleEquivalentOfArrayGet(aget_int); 345 } 346 // Replace the original int/long instruction. Note that it may have phi 347 // uses, environment uses, as well as real uses (from untyped ArraySets). 348 // We need to re-run primitive type propagation on its dependent instructions. 349 aget_int->ReplaceWith(aget_float); 350 aget_int->GetBlock()->RemoveInstruction(aget_int); 351 AddDependentInstructionsToWorklist(aget_float, &worklist); 352 } 353 } 354 355 // Set a flag stating that types of ArrayGets have been resolved. Requesting 356 // equivalent of the wrong type with GetFloatOrDoubleEquivalentOfArrayGet 357 // will fail from now on. 358 agets_fixed_ = true; 359 360 for (HArraySet* aset : ambiguous_asets_) { 361 HInstruction* array = aset->GetArray(); 362 if (!array->GetReferenceTypeInfo().IsPrimitiveArrayClass()) { 363 // RTP did not type the input array. Bail. 364 return false; 365 } 366 367 HInstruction* value = aset->GetValue(); 368 Primitive::Type value_type = value->GetType(); 369 Primitive::Type array_type = GetPrimitiveArrayComponentType(array); 370 DCHECK_EQ(Primitive::Is64BitType(value_type), Primitive::Is64BitType(array_type)); 371 372 if (Primitive::IsFloatingPointType(array_type)) { 373 if (!Primitive::IsFloatingPointType(value_type)) { 374 DCHECK(Primitive::IsIntegralType(value_type)); 375 // Array elements are floating-point but the value has not been replaced 376 // with its floating-point equivalent. The replacement must always 377 // succeed in code validated by the verifier. 378 HInstruction* equivalent = GetFloatOrDoubleEquivalent(value, array_type); 379 DCHECK(equivalent != nullptr); 380 aset->ReplaceInput(equivalent, /* input_index */ 2); 381 if (equivalent->IsPhi()) { 382 // Returned equivalent is a phi which may not have had its inputs 383 // replaced yet. We need to run primitive type propagation on it. 384 worklist.push_back(equivalent->AsPhi()); 385 } 386 } 387 // Refine the side effects of this floating point aset. Note that we do this even if 388 // no replacement occurs, since the right-hand-side may have been corrected already. 389 aset->ComputeSideEffects(); 390 } else { 391 // Array elements are integral and the value assigned to it initially 392 // was integral too. Nothing to do. 393 DCHECK(Primitive::IsIntegralType(array_type)); 394 DCHECK(Primitive::IsIntegralType(value_type)); 395 } 396 } 397 } 398 399 if (!worklist.empty()) { 400 ProcessPrimitiveTypePropagationWorklist(&worklist); 401 EquivalentPhisCleanup(); 402 } 403 404 return true; 405} 406 407static bool HasAliasInEnvironments(HInstruction* instruction) { 408 HEnvironment* last_user = nullptr; 409 for (const HUseListNode<HEnvironment*>& use : instruction->GetEnvUses()) { 410 DCHECK(use.GetUser() != nullptr); 411 // Note: The first comparison (== null) always fails. 412 if (use.GetUser() == last_user) { 413 return true; 414 } 415 last_user = use.GetUser(); 416 } 417 418 if (kIsDebugBuild) { 419 // Do a quadratic search to ensure same environment uses are next 420 // to each other. 421 const HUseList<HEnvironment*>& env_uses = instruction->GetEnvUses(); 422 for (auto current = env_uses.begin(), end = env_uses.end(); current != end; ++current) { 423 auto next = current; 424 for (++next; next != end; ++next) { 425 DCHECK(next->GetUser() != current->GetUser()); 426 } 427 } 428 } 429 return false; 430} 431 432void SsaBuilder::RemoveRedundantUninitializedStrings() { 433 if (graph_->IsDebuggable()) { 434 // Do not perform the optimization for consistency with the interpreter 435 // which always allocates an object for new-instance of String. 436 return; 437 } 438 439 for (HNewInstance* new_instance : uninitialized_strings_) { 440 DCHECK(new_instance->IsInBlock()); 441 DCHECK(new_instance->IsStringAlloc()); 442 443 // Replace NewInstance of String with NullConstant if not used prior to 444 // calling StringFactory. In case of deoptimization, the interpreter is 445 // expected to skip null check on the `this` argument of the StringFactory call. 446 if (!new_instance->HasNonEnvironmentUses() && !HasAliasInEnvironments(new_instance)) { 447 new_instance->ReplaceWith(graph_->GetNullConstant()); 448 new_instance->GetBlock()->RemoveInstruction(new_instance); 449 450 // Remove LoadClass if not needed any more. 451 HInstruction* input = new_instance->InputAt(0); 452 HLoadClass* load_class = nullptr; 453 454 // If the class was not present in the dex cache at the point of building 455 // the graph, the builder inserted a HClinitCheck in between. Since the String 456 // class is always initialized at the point of running Java code, we can remove 457 // that check. 458 if (input->IsClinitCheck()) { 459 load_class = input->InputAt(0)->AsLoadClass(); 460 input->ReplaceWith(load_class); 461 input->GetBlock()->RemoveInstruction(input); 462 } else { 463 load_class = input->AsLoadClass(); 464 DCHECK(new_instance->IsStringAlloc()); 465 DCHECK(!load_class->NeedsAccessCheck()) << "String class is always accessible"; 466 } 467 DCHECK(load_class != nullptr); 468 if (!load_class->HasUses()) { 469 // Even if the HLoadClass needs access check, we can remove it, as we know the 470 // String class does not need it. 471 load_class->GetBlock()->RemoveInstruction(load_class); 472 } 473 } 474 } 475} 476 477GraphAnalysisResult SsaBuilder::BuildSsa() { 478 DCHECK(!graph_->IsInSsaForm()); 479 480 // 1) Propagate types of phis. At this point, phis are typed void in the general 481 // case, or float/double/reference if we created an equivalent phi. So we need 482 // to propagate the types across phis to give them a correct type. If a type 483 // conflict is detected in this stage, the phi is marked dead. 484 RunPrimitiveTypePropagation(); 485 486 // 2) Now that the correct primitive types have been assigned, we can get rid 487 // of redundant phis. Note that we cannot do this phase before type propagation, 488 // otherwise we could get rid of phi equivalents, whose presence is a requirement 489 // for the type propagation phase. Note that this is to satisfy statement (a) 490 // of the SsaBuilder (see ssa_builder.h). 491 SsaRedundantPhiElimination(graph_).Run(); 492 493 // 3) Fix the type for null constants which are part of an equality comparison. 494 // We need to do this after redundant phi elimination, to ensure the only cases 495 // that we can see are reference comparison against 0. The redundant phi 496 // elimination ensures we do not see a phi taking two 0 constants in a HEqual 497 // or HNotEqual. 498 FixNullConstantType(); 499 500 // 4) Compute type of reference type instructions. The pass assumes that 501 // NullConstant has been fixed up. 502 ReferenceTypePropagation(graph_, 503 class_loader_, 504 dex_cache_, 505 handles_, 506 /* 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 */ 557HFloatConstant* 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 */ 579HDoubleConstant* 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 */ 602HPhi* 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 HInputsRef inputs = phi->GetInputs(); 619 HPhi* new_phi = 620 new (allocator) HPhi(allocator, phi->GetRegNumber(), inputs.size(), type); 621 // Copy the inputs. Note that the graph may not be correctly typed 622 // by doing this copy, but the type propagation phase will fix it. 623 ArrayRef<HUserRecord<HInstruction*>> new_input_records = new_phi->GetInputRecords(); 624 for (size_t i = 0; i < inputs.size(); ++i) { 625 new_input_records[i] = HUserRecord<HInstruction*>(inputs[i]); 626 } 627 phi->GetBlock()->InsertPhiAfter(new_phi, phi); 628 DCHECK(new_phi->IsLive()); 629 return new_phi; 630 } else { 631 // An existing equivalent was found. If it is dead, conflict was previously 632 // identified and we return nullptr instead. 633 HPhi* next_phi = next->AsPhi(); 634 DCHECK_EQ(next_phi->GetType(), type); 635 return next_phi->IsLive() ? next_phi : nullptr; 636 } 637} 638 639HArrayGet* SsaBuilder::GetFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget) { 640 DCHECK(Primitive::IsIntegralType(aget->GetType())); 641 642 if (!Primitive::IsIntOrLongType(aget->GetType())) { 643 // Cannot type boolean, char, byte, short to float/double. 644 return nullptr; 645 } 646 647 DCHECK(ContainsElement(ambiguous_agets_, aget)); 648 if (agets_fixed_) { 649 // This used to be an ambiguous ArrayGet but its type has been resolved to 650 // int/long. Requesting a float/double equivalent should lead to a conflict. 651 if (kIsDebugBuild) { 652 ScopedObjectAccess soa(Thread::Current()); 653 DCHECK(Primitive::IsIntOrLongType(GetPrimitiveArrayComponentType(aget->GetArray()))); 654 } 655 return nullptr; 656 } else { 657 // This is an ambiguous ArrayGet which has not been resolved yet. Return an 658 // equivalent float/double instruction to use until it is resolved. 659 HArrayGet* equivalent = FindFloatOrDoubleEquivalentOfArrayGet(aget); 660 return (equivalent == nullptr) ? CreateFloatOrDoubleEquivalentOfArrayGet(aget) : equivalent; 661 } 662} 663 664HInstruction* SsaBuilder::GetFloatOrDoubleEquivalent(HInstruction* value, Primitive::Type type) { 665 if (value->IsArrayGet()) { 666 return GetFloatOrDoubleEquivalentOfArrayGet(value->AsArrayGet()); 667 } else if (value->IsLongConstant()) { 668 return GetDoubleEquivalent(value->AsLongConstant()); 669 } else if (value->IsIntConstant()) { 670 return GetFloatEquivalent(value->AsIntConstant()); 671 } else if (value->IsPhi()) { 672 return GetFloatDoubleOrReferenceEquivalentOfPhi(value->AsPhi(), type); 673 } else { 674 return nullptr; 675 } 676} 677 678HInstruction* SsaBuilder::GetReferenceTypeEquivalent(HInstruction* value) { 679 if (value->IsIntConstant() && value->AsIntConstant()->GetValue() == 0) { 680 return graph_->GetNullConstant(); 681 } else if (value->IsPhi()) { 682 return GetFloatDoubleOrReferenceEquivalentOfPhi(value->AsPhi(), Primitive::kPrimNot); 683 } else { 684 return nullptr; 685 } 686} 687 688} // namespace art 689