ssa_builder.cc revision b11fc61d9769753ec9e4a51b88ee288923159283
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 "nodes.h" 20#include "primitive_type_propagation.h" 21#include "ssa_phi_elimination.h" 22 23namespace art { 24 25/** 26 * A debuggable application may require to reviving phis, to ensure their 27 * associated DEX register is available to a debugger. This class implements 28 * the logic for statement (c) of the SsaBuilder (see ssa_builder.h). It 29 * also makes sure that phis with incompatible input types are not revived 30 * (statement (b) of the SsaBuilder). 31 * 32 * This phase must be run after detecting dead phis through the 33 * DeadPhiElimination phase, and before deleting the dead phis. 34 */ 35class DeadPhiHandling : public ValueObject { 36 public: 37 explicit DeadPhiHandling(HGraph* graph) 38 : graph_(graph), worklist_(graph->GetArena()->Adapter(kArenaAllocSsaBuilder)) { 39 worklist_.reserve(kDefaultWorklistSize); 40 } 41 42 void Run(); 43 44 private: 45 void VisitBasicBlock(HBasicBlock* block); 46 void ProcessWorklist(); 47 void AddToWorklist(HPhi* phi); 48 void AddDependentInstructionsToWorklist(HPhi* phi); 49 bool UpdateType(HPhi* phi); 50 51 HGraph* const graph_; 52 ArenaVector<HPhi*> worklist_; 53 54 static constexpr size_t kDefaultWorklistSize = 8; 55 56 DISALLOW_COPY_AND_ASSIGN(DeadPhiHandling); 57}; 58 59static bool HasConflictingEquivalent(HPhi* phi) { 60 if (phi->GetNext() == nullptr) { 61 return false; 62 } 63 HPhi* next = phi->GetNext()->AsPhi(); 64 if (next->GetRegNumber() == phi->GetRegNumber()) { 65 if (next->GetType() == Primitive::kPrimVoid) { 66 // We only get a void type for an equivalent phi we processed and found out 67 // it was conflicting. 68 return true; 69 } else { 70 // Go to the next phi, in case it is also an equivalent. 71 return HasConflictingEquivalent(next); 72 } 73 } 74 return false; 75} 76 77bool DeadPhiHandling::UpdateType(HPhi* phi) { 78 if (phi->IsDead()) { 79 // Phi was rendered dead while waiting in the worklist because it was replaced 80 // with an equivalent. 81 return false; 82 } 83 84 Primitive::Type existing = phi->GetType(); 85 86 bool conflict = false; 87 Primitive::Type new_type = existing; 88 for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { 89 HInstruction* input = phi->InputAt(i); 90 if (input->IsPhi() && input->AsPhi()->IsDead()) { 91 // We are doing a reverse post order visit of the graph, reviving 92 // phis that have environment uses and updating their types. If an 93 // input is a phi, and it is dead (because its input types are 94 // conflicting), this phi must be marked dead as well. 95 conflict = true; 96 break; 97 } 98 Primitive::Type input_type = HPhi::ToPhiType(input->GetType()); 99 100 // The only acceptable transitions are: 101 // - From void to typed: first time we update the type of this phi. 102 // - From int to reference (or reference to int): the phi has to change 103 // to reference type. If the integer input cannot be converted to a 104 // reference input, the phi will remain dead. 105 if (new_type == Primitive::kPrimVoid) { 106 new_type = input_type; 107 } else if (new_type == Primitive::kPrimNot && input_type == Primitive::kPrimInt) { 108 if (input->IsPhi() && HasConflictingEquivalent(input->AsPhi())) { 109 // If we already asked for an equivalent of the input phi, but that equivalent 110 // ended up conflicting, make this phi conflicting too. 111 conflict = true; 112 break; 113 } 114 HInstruction* equivalent = SsaBuilder::GetReferenceTypeEquivalent(input); 115 if (equivalent == nullptr) { 116 conflict = true; 117 break; 118 } 119 phi->ReplaceInput(equivalent, i); 120 if (equivalent->IsPhi()) { 121 DCHECK_EQ(equivalent->GetType(), Primitive::kPrimNot); 122 // We created a new phi, but that phi has the same inputs as the old phi. We 123 // add it to the worklist to ensure its inputs can also be converted to reference. 124 // If not, it will remain dead, and the algorithm will make the current phi dead 125 // as well. 126 equivalent->AsPhi()->SetLive(); 127 AddToWorklist(equivalent->AsPhi()); 128 } 129 } else if (new_type == Primitive::kPrimInt && input_type == Primitive::kPrimNot) { 130 new_type = Primitive::kPrimNot; 131 // Start over, we may request reference equivalents for the inputs of the phi. 132 i = -1; 133 } else if (new_type != input_type) { 134 conflict = true; 135 break; 136 } 137 } 138 139 if (conflict) { 140 phi->SetType(Primitive::kPrimVoid); 141 phi->SetDead(); 142 return true; 143 } else if (existing == new_type) { 144 return false; 145 } 146 147 DCHECK(phi->IsLive()); 148 phi->SetType(new_type); 149 150 // There might exist a `new_type` equivalent of `phi` already. In that case, 151 // we replace the equivalent with the, now live, `phi`. 152 HPhi* equivalent = phi->GetNextEquivalentPhiWithSameType(); 153 if (equivalent != nullptr) { 154 // There cannot be more than two equivalents with the same type. 155 DCHECK(equivalent->GetNextEquivalentPhiWithSameType() == nullptr); 156 // If doing fix-point iteration, the equivalent might be in `worklist_`. 157 // Setting it dead will make UpdateType skip it. 158 equivalent->SetDead(); 159 equivalent->ReplaceWith(phi); 160 } 161 162 return true; 163} 164 165void DeadPhiHandling::VisitBasicBlock(HBasicBlock* block) { 166 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 167 HPhi* phi = it.Current()->AsPhi(); 168 if (phi->IsDead() && phi->HasEnvironmentUses()) { 169 phi->SetLive(); 170 if (block->IsLoopHeader()) { 171 // Give a type to the loop phi to guarantee convergence of the algorithm. 172 // Note that the dead phi may already have a type if it is an equivalent 173 // generated for a typed LoadLocal. In that case we do not change the 174 // type because it could lead to an unsupported PrimNot/Float/Double -> 175 // PrimInt/Long transition and create same type equivalents. 176 if (phi->GetType() == Primitive::kPrimVoid) { 177 phi->SetType(phi->InputAt(0)->GetType()); 178 } 179 AddToWorklist(phi); 180 } else { 181 // Because we are doing a reverse post order visit, all inputs of 182 // this phi have been visited and therefore had their (initial) type set. 183 UpdateType(phi); 184 } 185 } 186 } 187} 188 189void DeadPhiHandling::ProcessWorklist() { 190 while (!worklist_.empty()) { 191 HPhi* instruction = worklist_.back(); 192 worklist_.pop_back(); 193 // Note that the same equivalent phi can be added multiple times in the work list, if 194 // used by multiple phis. The first call to `UpdateType` will know whether the phi is 195 // dead or live. 196 if (instruction->IsLive() && UpdateType(instruction)) { 197 AddDependentInstructionsToWorklist(instruction); 198 } 199 } 200} 201 202void DeadPhiHandling::AddToWorklist(HPhi* instruction) { 203 DCHECK(instruction->IsLive()); 204 worklist_.push_back(instruction); 205} 206 207void DeadPhiHandling::AddDependentInstructionsToWorklist(HPhi* instruction) { 208 for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) { 209 HPhi* phi = it.Current()->GetUser()->AsPhi(); 210 if (phi != nullptr && !phi->IsDead()) { 211 AddToWorklist(phi); 212 } 213 } 214} 215 216void DeadPhiHandling::Run() { 217 for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 218 VisitBasicBlock(it.Current()); 219 } 220 ProcessWorklist(); 221} 222 223void SsaBuilder::FixNullConstantType() { 224 // The order doesn't matter here. 225 for (HReversePostOrderIterator itb(*GetGraph()); !itb.Done(); itb.Advance()) { 226 for (HInstructionIterator it(itb.Current()->GetInstructions()); !it.Done(); it.Advance()) { 227 HInstruction* equality_instr = it.Current(); 228 if (!equality_instr->IsEqual() && !equality_instr->IsNotEqual()) { 229 continue; 230 } 231 HInstruction* left = equality_instr->InputAt(0); 232 HInstruction* right = equality_instr->InputAt(1); 233 HInstruction* int_operand = nullptr; 234 235 if ((left->GetType() == Primitive::kPrimNot) && (right->GetType() == Primitive::kPrimInt)) { 236 int_operand = right; 237 } else if ((right->GetType() == Primitive::kPrimNot) 238 && (left->GetType() == Primitive::kPrimInt)) { 239 int_operand = left; 240 } else { 241 continue; 242 } 243 244 // If we got here, we are comparing against a reference and the int constant 245 // should be replaced with a null constant. 246 // Both type propagation and redundant phi elimination ensure `int_operand` 247 // can only be the 0 constant. 248 DCHECK(int_operand->IsIntConstant()); 249 DCHECK_EQ(0, int_operand->AsIntConstant()->GetValue()); 250 equality_instr->ReplaceInput(GetGraph()->GetNullConstant(), int_operand == right ? 1 : 0); 251 } 252 } 253} 254 255void SsaBuilder::EquivalentPhisCleanup() { 256 // The order doesn't matter here. 257 for (HReversePostOrderIterator itb(*GetGraph()); !itb.Done(); itb.Advance()) { 258 for (HInstructionIterator it(itb.Current()->GetPhis()); !it.Done(); it.Advance()) { 259 HPhi* phi = it.Current()->AsPhi(); 260 HPhi* next = phi->GetNextEquivalentPhiWithSameType(); 261 if (next != nullptr) { 262 // Make sure we do not replace a live phi with a dead phi. A live phi has been 263 // handled by the type propagation phase, unlike a dead phi. 264 if (next->IsLive()) { 265 phi->ReplaceWith(next); 266 } else { 267 next->ReplaceWith(phi); 268 } 269 DCHECK(next->GetNextEquivalentPhiWithSameType() == nullptr) 270 << "More then one phi equivalent with type " << phi->GetType() 271 << " found for phi" << phi->GetId(); 272 } 273 } 274 } 275} 276 277void SsaBuilder::BuildSsa() { 278 // 1) Visit in reverse post order. We need to have all predecessors of a block visited 279 // (with the exception of loops) in order to create the right environment for that 280 // block. For loops, we create phis whose inputs will be set in 2). 281 for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) { 282 VisitBasicBlock(it.Current()); 283 } 284 285 // 2) Set inputs of loop phis. 286 for (HBasicBlock* block : loop_headers_) { 287 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 288 HPhi* phi = it.Current()->AsPhi(); 289 for (HBasicBlock* predecessor : block->GetPredecessors()) { 290 HInstruction* input = ValueOfLocal(predecessor, phi->GetRegNumber()); 291 phi->AddInput(input); 292 } 293 } 294 } 295 296 // 3) Mark dead phis. This will mark phis that are only used by environments: 297 // at the DEX level, the type of these phis does not need to be consistent, but 298 // our code generator will complain if the inputs of a phi do not have the same 299 // type. The marking allows the type propagation to know which phis it needs 300 // to handle. We mark but do not eliminate: the elimination will be done in 301 // step 9). 302 SsaDeadPhiElimination dead_phis_for_type_propagation(GetGraph()); 303 dead_phis_for_type_propagation.MarkDeadPhis(); 304 305 // 4) Propagate types of phis. At this point, phis are typed void in the general 306 // case, or float/double/reference when we created an equivalent phi. So we 307 // need to propagate the types across phis to give them a correct type. 308 PrimitiveTypePropagation type_propagation(GetGraph()); 309 type_propagation.Run(); 310 311 // 5) When creating equivalent phis we copy the inputs of the original phi which 312 // may be improperly typed. This was fixed during the type propagation in 4) but 313 // as a result we may end up with two equivalent phis with the same type for 314 // the same dex register. This pass cleans them up. 315 EquivalentPhisCleanup(); 316 317 // 6) Mark dead phis again. Step 4) may have introduced new phis. 318 // Step 5) might enable the death of new phis. 319 SsaDeadPhiElimination dead_phis(GetGraph()); 320 dead_phis.MarkDeadPhis(); 321 322 // 7) Now that the graph is correctly typed, we can get rid of redundant phis. 323 // Note that we cannot do this phase before type propagation, otherwise 324 // we could get rid of phi equivalents, whose presence is a requirement for the 325 // type propagation phase. Note that this is to satisfy statement (a) of the 326 // SsaBuilder (see ssa_builder.h). 327 SsaRedundantPhiElimination redundant_phi(GetGraph()); 328 redundant_phi.Run(); 329 330 // 8) Fix the type for null constants which are part of an equality comparison. 331 // We need to do this after redundant phi elimination, to ensure the only cases 332 // that we can see are reference comparison against 0. The redundant phi 333 // elimination ensures we do not see a phi taking two 0 constants in a HEqual 334 // or HNotEqual. 335 FixNullConstantType(); 336 337 // 9) Make sure environments use the right phi "equivalent": a phi marked dead 338 // can have a phi equivalent that is not dead. We must therefore update 339 // all environment uses of the dead phi to use its equivalent. Note that there 340 // can be multiple phis for the same Dex register that are live (for example 341 // when merging constants), in which case it is OK for the environments 342 // to just reference one. 343 for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) { 344 HBasicBlock* block = it.Current(); 345 for (HInstructionIterator it_phis(block->GetPhis()); !it_phis.Done(); it_phis.Advance()) { 346 HPhi* phi = it_phis.Current()->AsPhi(); 347 // If the phi is not dead, or has no environment uses, there is nothing to do. 348 if (!phi->IsDead() || !phi->HasEnvironmentUses()) continue; 349 HInstruction* next = phi->GetNext(); 350 if (!phi->IsVRegEquivalentOf(next)) continue; 351 if (next->AsPhi()->IsDead()) { 352 // If the phi equivalent is dead, check if there is another one. 353 next = next->GetNext(); 354 if (!phi->IsVRegEquivalentOf(next)) continue; 355 // There can be at most two phi equivalents. 356 DCHECK(!phi->IsVRegEquivalentOf(next->GetNext())); 357 if (next->AsPhi()->IsDead()) continue; 358 } 359 // We found a live phi equivalent. Update the environment uses of `phi` with it. 360 phi->ReplaceWith(next); 361 } 362 } 363 364 // 10) Deal with phis to guarantee liveness of phis in case of a debuggable 365 // application. This is for satisfying statement (c) of the SsaBuilder 366 // (see ssa_builder.h). 367 if (GetGraph()->IsDebuggable()) { 368 DeadPhiHandling dead_phi_handler(GetGraph()); 369 dead_phi_handler.Run(); 370 } 371 372 // 11) Now that the right phis are used for the environments, and we 373 // have potentially revive dead phis in case of a debuggable application, 374 // we can eliminate phis we do not need. Regardless of the debuggable status, 375 // this phase is necessary for statement (b) of the SsaBuilder (see ssa_builder.h), 376 // as well as for the code generation, which does not deal with phis of conflicting 377 // input types. 378 dead_phis.EliminateDeadPhis(); 379 380 // 12) Clear locals. 381 for (HInstructionIterator it(GetGraph()->GetEntryBlock()->GetInstructions()); 382 !it.Done(); 383 it.Advance()) { 384 HInstruction* current = it.Current(); 385 if (current->IsLocal()) { 386 current->GetBlock()->RemoveInstruction(current); 387 } 388 } 389} 390 391ArenaVector<HInstruction*>* SsaBuilder::GetLocalsFor(HBasicBlock* block) { 392 DCHECK_LT(block->GetBlockId(), locals_for_.size()); 393 ArenaVector<HInstruction*>* locals = &locals_for_[block->GetBlockId()]; 394 const size_t vregs = GetGraph()->GetNumberOfVRegs(); 395 if (locals->empty() && vregs != 0u) { 396 locals->resize(vregs, nullptr); 397 398 if (block->IsCatchBlock()) { 399 ArenaAllocator* arena = GetGraph()->GetArena(); 400 // We record incoming inputs of catch phis at throwing instructions and 401 // must therefore eagerly create the phis. Phis for undefined vregs will 402 // be deleted when the first throwing instruction with the vreg undefined 403 // is encountered. Unused phis will be removed by dead phi analysis. 404 for (size_t i = 0; i < vregs; ++i) { 405 // No point in creating the catch phi if it is already undefined at 406 // the first throwing instruction. 407 if ((*current_locals_)[i] != nullptr) { 408 HPhi* phi = new (arena) HPhi(arena, i, 0, Primitive::kPrimVoid); 409 block->AddPhi(phi); 410 (*locals)[i] = phi; 411 } 412 } 413 } 414 } 415 return locals; 416} 417 418HInstruction* SsaBuilder::ValueOfLocal(HBasicBlock* block, size_t local) { 419 ArenaVector<HInstruction*>* locals = GetLocalsFor(block); 420 DCHECK_LT(local, locals->size()); 421 return (*locals)[local]; 422} 423 424void SsaBuilder::VisitBasicBlock(HBasicBlock* block) { 425 current_locals_ = GetLocalsFor(block); 426 427 if (block->IsCatchBlock()) { 428 // Catch phis were already created and inputs collected from throwing sites. 429 if (kIsDebugBuild) { 430 // Make sure there was at least one throwing instruction which initialized 431 // locals (guaranteed by HGraphBuilder) and that all try blocks have been 432 // visited already (from HTryBoundary scoping and reverse post order). 433 bool throwing_instruction_found = false; 434 bool catch_block_visited = false; 435 for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) { 436 HBasicBlock* current = it.Current(); 437 if (current == block) { 438 catch_block_visited = true; 439 } else if (current->IsTryBlock() && 440 current->GetTryCatchInformation()->GetTryEntry().HasExceptionHandler(*block)) { 441 DCHECK(!catch_block_visited) << "Catch block visited before its try block."; 442 throwing_instruction_found |= current->HasThrowingInstructions(); 443 } 444 } 445 DCHECK(throwing_instruction_found) << "No instructions throwing into a live catch block."; 446 } 447 } else if (block->IsLoopHeader()) { 448 // If the block is a loop header, we know we only have visited the pre header 449 // because we are visiting in reverse post order. We create phis for all initialized 450 // locals from the pre header. Their inputs will be populated at the end of 451 // the analysis. 452 for (size_t local = 0; local < current_locals_->size(); ++local) { 453 HInstruction* incoming = ValueOfLocal(block->GetLoopInformation()->GetPreHeader(), local); 454 if (incoming != nullptr) { 455 HPhi* phi = new (GetGraph()->GetArena()) HPhi( 456 GetGraph()->GetArena(), local, 0, Primitive::kPrimVoid); 457 block->AddPhi(phi); 458 (*current_locals_)[local] = phi; 459 } 460 } 461 // Save the loop header so that the last phase of the analysis knows which 462 // blocks need to be updated. 463 loop_headers_.push_back(block); 464 } else if (block->GetPredecessors().size() > 0) { 465 // All predecessors have already been visited because we are visiting in reverse post order. 466 // We merge the values of all locals, creating phis if those values differ. 467 for (size_t local = 0; local < current_locals_->size(); ++local) { 468 bool one_predecessor_has_no_value = false; 469 bool is_different = false; 470 HInstruction* value = ValueOfLocal(block->GetPredecessor(0), local); 471 472 for (HBasicBlock* predecessor : block->GetPredecessors()) { 473 HInstruction* current = ValueOfLocal(predecessor, local); 474 if (current == nullptr) { 475 one_predecessor_has_no_value = true; 476 break; 477 } else if (current != value) { 478 is_different = true; 479 } 480 } 481 482 if (one_predecessor_has_no_value) { 483 // If one predecessor has no value for this local, we trust the verifier has 484 // successfully checked that there is a store dominating any read after this block. 485 continue; 486 } 487 488 if (is_different) { 489 HPhi* phi = new (GetGraph()->GetArena()) HPhi( 490 GetGraph()->GetArena(), local, block->GetPredecessors().size(), Primitive::kPrimVoid); 491 for (size_t i = 0; i < block->GetPredecessors().size(); i++) { 492 HInstruction* pred_value = ValueOfLocal(block->GetPredecessor(i), local); 493 phi->SetRawInputAt(i, pred_value); 494 } 495 block->AddPhi(phi); 496 value = phi; 497 } 498 (*current_locals_)[local] = value; 499 } 500 } 501 502 // Visit all instructions. The instructions of interest are: 503 // - HLoadLocal: replace them with the current value of the local. 504 // - HStoreLocal: update current value of the local and remove the instruction. 505 // - Instructions that require an environment: populate their environment 506 // with the current values of the locals. 507 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 508 it.Current()->Accept(this); 509 } 510} 511 512/** 513 * Constants in the Dex format are not typed. So the builder types them as 514 * integers, but when doing the SSA form, we might realize the constant 515 * is used for floating point operations. We create a floating-point equivalent 516 * constant to make the operations correctly typed. 517 */ 518HFloatConstant* SsaBuilder::GetFloatEquivalent(HIntConstant* constant) { 519 // We place the floating point constant next to this constant. 520 HFloatConstant* result = constant->GetNext()->AsFloatConstant(); 521 if (result == nullptr) { 522 HGraph* graph = constant->GetBlock()->GetGraph(); 523 ArenaAllocator* allocator = graph->GetArena(); 524 result = new (allocator) HFloatConstant(bit_cast<float, int32_t>(constant->GetValue())); 525 constant->GetBlock()->InsertInstructionBefore(result, constant->GetNext()); 526 graph->CacheFloatConstant(result); 527 } else { 528 // If there is already a constant with the expected type, we know it is 529 // the floating point equivalent of this constant. 530 DCHECK_EQ((bit_cast<int32_t, float>(result->GetValue())), constant->GetValue()); 531 } 532 return result; 533} 534 535/** 536 * Wide constants in the Dex format are not typed. So the builder types them as 537 * longs, but when doing the SSA form, we might realize the constant 538 * is used for floating point operations. We create a floating-point equivalent 539 * constant to make the operations correctly typed. 540 */ 541HDoubleConstant* SsaBuilder::GetDoubleEquivalent(HLongConstant* constant) { 542 // We place the floating point constant next to this constant. 543 HDoubleConstant* result = constant->GetNext()->AsDoubleConstant(); 544 if (result == nullptr) { 545 HGraph* graph = constant->GetBlock()->GetGraph(); 546 ArenaAllocator* allocator = graph->GetArena(); 547 result = new (allocator) HDoubleConstant(bit_cast<double, int64_t>(constant->GetValue())); 548 constant->GetBlock()->InsertInstructionBefore(result, constant->GetNext()); 549 graph->CacheDoubleConstant(result); 550 } else { 551 // If there is already a constant with the expected type, we know it is 552 // the floating point equivalent of this constant. 553 DCHECK_EQ((bit_cast<int64_t, double>(result->GetValue())), constant->GetValue()); 554 } 555 return result; 556} 557 558/** 559 * Because of Dex format, we might end up having the same phi being 560 * used for non floating point operations and floating point / reference operations. 561 * Because we want the graph to be correctly typed (and thereafter avoid moves between 562 * floating point registers and core registers), we need to create a copy of the 563 * phi with a floating point / reference type. 564 */ 565HPhi* SsaBuilder::GetFloatDoubleOrReferenceEquivalentOfPhi(HPhi* phi, Primitive::Type type) { 566 // We place the floating point /reference phi next to this phi. 567 HInstruction* next = phi->GetNext(); 568 if (next != nullptr 569 && next->AsPhi()->GetRegNumber() == phi->GetRegNumber() 570 && next->GetType() != type) { 571 // Move to the next phi to see if it is the one we are looking for. 572 next = next->GetNext(); 573 } 574 575 if (next == nullptr 576 || (next->AsPhi()->GetRegNumber() != phi->GetRegNumber()) 577 || (next->GetType() != type)) { 578 ArenaAllocator* allocator = phi->GetBlock()->GetGraph()->GetArena(); 579 HPhi* new_phi = new (allocator) HPhi(allocator, phi->GetRegNumber(), phi->InputCount(), type); 580 for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { 581 // Copy the inputs. Note that the graph may not be correctly typed by doing this copy, 582 // but the type propagation phase will fix it. 583 new_phi->SetRawInputAt(i, phi->InputAt(i)); 584 } 585 phi->GetBlock()->InsertPhiAfter(new_phi, phi); 586 return new_phi; 587 } else { 588 DCHECK_EQ(next->GetType(), type); 589 return next->AsPhi(); 590 } 591} 592 593HInstruction* SsaBuilder::GetFloatOrDoubleEquivalent(HInstruction* user, 594 HInstruction* value, 595 Primitive::Type type) { 596 if (value->IsArrayGet()) { 597 // The verifier has checked that values in arrays cannot be used for both 598 // floating point and non-floating point operations. It is therefore safe to just 599 // change the type of the operation. 600 value->AsArrayGet()->SetType(type); 601 return value; 602 } else if (value->IsLongConstant()) { 603 return GetDoubleEquivalent(value->AsLongConstant()); 604 } else if (value->IsIntConstant()) { 605 return GetFloatEquivalent(value->AsIntConstant()); 606 } else if (value->IsPhi()) { 607 return GetFloatDoubleOrReferenceEquivalentOfPhi(value->AsPhi(), type); 608 } else { 609 // For other instructions, we assume the verifier has checked that the dex format is correctly 610 // typed and the value in a dex register will not be used for both floating point and 611 // non-floating point operations. So the only reason an instruction would want a floating 612 // point equivalent is for an unused phi that will be removed by the dead phi elimination phase. 613 DCHECK(user->IsPhi()) << "is actually " << user->DebugName() << " (" << user->GetId() << ")"; 614 return value; 615 } 616} 617 618HInstruction* SsaBuilder::GetReferenceTypeEquivalent(HInstruction* value) { 619 if (value->IsIntConstant() && value->AsIntConstant()->GetValue() == 0) { 620 return value->GetBlock()->GetGraph()->GetNullConstant(); 621 } else if (value->IsPhi()) { 622 return GetFloatDoubleOrReferenceEquivalentOfPhi(value->AsPhi(), Primitive::kPrimNot); 623 } else { 624 return nullptr; 625 } 626} 627 628void SsaBuilder::VisitLoadLocal(HLoadLocal* load) { 629 DCHECK_LT(load->GetLocal()->GetRegNumber(), current_locals_->size()); 630 HInstruction* value = (*current_locals_)[load->GetLocal()->GetRegNumber()]; 631 // If the operation requests a specific type, we make sure its input is of that type. 632 if (load->GetType() != value->GetType()) { 633 if (load->GetType() == Primitive::kPrimFloat || load->GetType() == Primitive::kPrimDouble) { 634 value = GetFloatOrDoubleEquivalent(load, value, load->GetType()); 635 } else if (load->GetType() == Primitive::kPrimNot) { 636 value = GetReferenceTypeEquivalent(value); 637 } 638 } 639 load->ReplaceWith(value); 640 load->GetBlock()->RemoveInstruction(load); 641} 642 643void SsaBuilder::VisitStoreLocal(HStoreLocal* store) { 644 DCHECK_LT(store->GetLocal()->GetRegNumber(), current_locals_->size()); 645 (*current_locals_)[store->GetLocal()->GetRegNumber()] = store->InputAt(1); 646 store->GetBlock()->RemoveInstruction(store); 647} 648 649void SsaBuilder::VisitInstruction(HInstruction* instruction) { 650 if (instruction->NeedsEnvironment()) { 651 HEnvironment* environment = new (GetGraph()->GetArena()) HEnvironment( 652 GetGraph()->GetArena(), 653 current_locals_->size(), 654 GetGraph()->GetDexFile(), 655 GetGraph()->GetMethodIdx(), 656 instruction->GetDexPc(), 657 GetGraph()->GetInvokeType(), 658 instruction); 659 environment->CopyFrom(*current_locals_); 660 instruction->SetRawEnvironment(environment); 661 } 662 663 // If in a try block, propagate values of locals into catch blocks. 664 if (instruction->CanThrowIntoCatchBlock()) { 665 const HTryBoundary& try_entry = 666 instruction->GetBlock()->GetTryCatchInformation()->GetTryEntry(); 667 for (HExceptionHandlerIterator it(try_entry); !it.Done(); it.Advance()) { 668 HBasicBlock* catch_block = it.Current(); 669 ArenaVector<HInstruction*>* handler_locals = GetLocalsFor(catch_block); 670 DCHECK_EQ(handler_locals->size(), current_locals_->size()); 671 for (size_t vreg = 0, e = current_locals_->size(); vreg < e; ++vreg) { 672 HInstruction* handler_value = (*handler_locals)[vreg]; 673 if (handler_value == nullptr) { 674 // Vreg was undefined at a previously encountered throwing instruction 675 // and the catch phi was deleted. Do not record the local value. 676 continue; 677 } 678 DCHECK(handler_value->IsPhi()); 679 680 HInstruction* local_value = (*current_locals_)[vreg]; 681 if (local_value == nullptr) { 682 // This is the first instruction throwing into `catch_block` where 683 // `vreg` is undefined. Delete the catch phi. 684 catch_block->RemovePhi(handler_value->AsPhi()); 685 (*handler_locals)[vreg] = nullptr; 686 } else { 687 // Vreg has been defined at all instructions throwing into `catch_block` 688 // encountered so far. Record the local value in the catch phi. 689 handler_value->AsPhi()->AddInput(local_value); 690 } 691 } 692 } 693 } 694} 695 696void SsaBuilder::VisitTemporary(HTemporary* temp) { 697 // Temporaries are only used by the baseline register allocator. 698 temp->GetBlock()->RemoveInstruction(temp); 699} 700 701} // namespace art 702