ssa_builder.cc revision 8d5b8b295930aaa43255c4f0b74ece3ee8b43a47
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(), kDefaultWorklistSize) {} 39 40 void Run(); 41 42 private: 43 void VisitBasicBlock(HBasicBlock* block); 44 void ProcessWorklist(); 45 void AddToWorklist(HPhi* phi); 46 void AddDependentInstructionsToWorklist(HPhi* phi); 47 bool UpdateType(HPhi* phi); 48 49 HGraph* const graph_; 50 GrowableArray<HPhi*> worklist_; 51 52 static constexpr size_t kDefaultWorklistSize = 8; 53 54 DISALLOW_COPY_AND_ASSIGN(DeadPhiHandling); 55}; 56 57bool DeadPhiHandling::UpdateType(HPhi* phi) { 58 Primitive::Type existing = phi->GetType(); 59 DCHECK(phi->IsLive()); 60 61 bool conflict = false; 62 Primitive::Type new_type = existing; 63 for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { 64 HInstruction* input = phi->InputAt(i); 65 if (input->IsPhi() && input->AsPhi()->IsDead()) { 66 // We are doing a reverse post order visit of the graph, reviving 67 // phis that have environment uses and updating their types. If an 68 // input is a phi, and it is dead (because its input types are 69 // conflicting), this phi must be marked dead as well. 70 conflict = true; 71 break; 72 } 73 Primitive::Type input_type = HPhi::ToPhiType(input->GetType()); 74 75 // The only acceptable transitions are: 76 // - From void to typed: first time we update the type of this phi. 77 // - From int to reference (or reference to int): the phi has to change 78 // to reference type. If the integer input cannot be converted to a 79 // reference input, the phi will remain dead. 80 if (new_type == Primitive::kPrimVoid) { 81 new_type = input_type; 82 } else if (new_type == Primitive::kPrimNot && input_type == Primitive::kPrimInt) { 83 HInstruction* equivalent = SsaBuilder::GetReferenceTypeEquivalent(input); 84 if (equivalent == nullptr) { 85 conflict = true; 86 break; 87 } else { 88 phi->ReplaceInput(equivalent, i); 89 if (equivalent->IsPhi()) { 90 DCHECK_EQ(equivalent->GetType(), Primitive::kPrimNot); 91 // We created a new phi, but that phi has the same inputs as the old phi. We 92 // add it to the worklist to ensure its inputs can also be converted to reference. 93 // If not, it will remain dead, and the algorithm will make the current phi dead 94 // as well. 95 equivalent->AsPhi()->SetLive(); 96 AddToWorklist(equivalent->AsPhi()); 97 } 98 } 99 } else if (new_type == Primitive::kPrimInt && input_type == Primitive::kPrimNot) { 100 new_type = Primitive::kPrimNot; 101 // Start over, we may request reference equivalents for the inputs of the phi. 102 i = -1; 103 } else if (new_type != input_type) { 104 conflict = true; 105 break; 106 } 107 } 108 109 if (conflict) { 110 phi->SetType(Primitive::kPrimVoid); 111 phi->SetDead(); 112 return true; 113 } else { 114 DCHECK(phi->IsLive()); 115 phi->SetType(new_type); 116 return existing != new_type; 117 } 118} 119 120void DeadPhiHandling::VisitBasicBlock(HBasicBlock* block) { 121 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 122 HPhi* phi = it.Current()->AsPhi(); 123 if (phi->IsDead() && phi->HasEnvironmentUses()) { 124 phi->SetLive(); 125 if (block->IsLoopHeader()) { 126 // Give a type to the loop phi, to guarantee convergence of the algorithm. 127 phi->SetType(phi->InputAt(0)->GetType()); 128 AddToWorklist(phi); 129 } else { 130 // Because we are doing a reverse post order visit, all inputs of 131 // this phi have been visited and therefore had their (initial) type set. 132 UpdateType(phi); 133 } 134 } 135 } 136} 137 138void DeadPhiHandling::ProcessWorklist() { 139 while (!worklist_.IsEmpty()) { 140 HPhi* instruction = worklist_.Pop(); 141 // Note that the same equivalent phi can be added multiple times in the work list, if 142 // used by multiple phis. The first call to `UpdateType` will know whether the phi is 143 // dead or live. 144 if (instruction->IsLive() && UpdateType(instruction)) { 145 AddDependentInstructionsToWorklist(instruction); 146 } 147 } 148} 149 150void DeadPhiHandling::AddToWorklist(HPhi* instruction) { 151 DCHECK(instruction->IsLive()); 152 worklist_.Add(instruction); 153} 154 155void DeadPhiHandling::AddDependentInstructionsToWorklist(HPhi* instruction) { 156 for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) { 157 HPhi* phi = it.Current()->GetUser()->AsPhi(); 158 if (phi != nullptr && !phi->IsDead()) { 159 AddToWorklist(phi); 160 } 161 } 162} 163 164void DeadPhiHandling::Run() { 165 for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 166 VisitBasicBlock(it.Current()); 167 } 168 ProcessWorklist(); 169} 170 171static bool IsPhiEquivalentOf(HInstruction* instruction, HPhi* phi) { 172 return instruction != nullptr 173 && instruction->IsPhi() 174 && instruction->AsPhi()->GetRegNumber() == phi->GetRegNumber(); 175} 176 177void SsaBuilder::BuildSsa() { 178 // 1) Visit in reverse post order. We need to have all predecessors of a block visited 179 // (with the exception of loops) in order to create the right environment for that 180 // block. For loops, we create phis whose inputs will be set in 2). 181 for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) { 182 VisitBasicBlock(it.Current()); 183 } 184 185 // 2) Set inputs of loop phis. 186 for (size_t i = 0; i < loop_headers_.Size(); i++) { 187 HBasicBlock* block = loop_headers_.Get(i); 188 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 189 HPhi* phi = it.Current()->AsPhi(); 190 for (size_t pred = 0; pred < block->GetPredecessors().Size(); pred++) { 191 HInstruction* input = ValueOfLocal(block->GetPredecessors().Get(pred), phi->GetRegNumber()); 192 phi->AddInput(input); 193 } 194 } 195 } 196 197 // 3) Mark dead phis. This will mark phis that are only used by environments: 198 // at the DEX level, the type of these phis does not need to be consistent, but 199 // our code generator will complain if the inputs of a phi do not have the same 200 // type. The marking allows the type propagation to know which phis it needs 201 // to handle. We mark but do not eliminate: the elimination will be done in 202 // step 9). 203 SsaDeadPhiElimination dead_phis_for_type_propagation(GetGraph()); 204 dead_phis_for_type_propagation.MarkDeadPhis(); 205 206 // 4) Propagate types of phis. At this point, phis are typed void in the general 207 // case, or float/double/reference when we created an equivalent phi. So we 208 // need to propagate the types across phis to give them a correct type. 209 PrimitiveTypePropagation type_propagation(GetGraph()); 210 type_propagation.Run(); 211 212 // 5) Mark dead phis again. Steph 4) may have introduced new phis. 213 SsaDeadPhiElimination dead_phis(GetGraph()); 214 dead_phis.MarkDeadPhis(); 215 216 // 6) Now that the graph is correclty typed, we can get rid of redundant phis. 217 // Note that we cannot do this phase before type propagation, otherwise 218 // we could get rid of phi equivalents, whose presence is a requirement for the 219 // type propagation phase. Note that this is to satisfy statement (a) of the 220 // SsaBuilder (see ssa_builder.h). 221 SsaRedundantPhiElimination redundant_phi(GetGraph()); 222 redundant_phi.Run(); 223 224 // 7) Make sure environments use the right phi "equivalent": a phi marked dead 225 // can have a phi equivalent that is not dead. We must therefore update 226 // all environment uses of the dead phi to use its equivalent. Note that there 227 // can be multiple phis for the same Dex register that are live (for example 228 // when merging constants), in which case it is OK for the environments 229 // to just reference one. 230 for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) { 231 HBasicBlock* block = it.Current(); 232 for (HInstructionIterator it_phis(block->GetPhis()); !it_phis.Done(); it_phis.Advance()) { 233 HPhi* phi = it_phis.Current()->AsPhi(); 234 // If the phi is not dead, or has no environment uses, there is nothing to do. 235 if (!phi->IsDead() || !phi->HasEnvironmentUses()) continue; 236 HInstruction* next = phi->GetNext(); 237 if (!IsPhiEquivalentOf(next, phi)) continue; 238 if (next->AsPhi()->IsDead()) { 239 // If the phi equivalent is dead, check if there is another one. 240 next = next->GetNext(); 241 if (!IsPhiEquivalentOf(next, phi)) continue; 242 // There can be at most two phi equivalents. 243 DCHECK(!IsPhiEquivalentOf(next->GetNext(), phi)); 244 if (next->AsPhi()->IsDead()) continue; 245 } 246 // We found a live phi equivalent. Update the environment uses of `phi` with it. 247 phi->ReplaceWith(next); 248 } 249 } 250 251 // 8) Deal with phis to guarantee liveness of phis in case of a debuggable 252 // application. This is for satisfying statement (c) of the SsaBuilder 253 // (see ssa_builder.h). 254 if (GetGraph()->IsDebuggable()) { 255 DeadPhiHandling dead_phi_handler(GetGraph()); 256 dead_phi_handler.Run(); 257 } 258 259 // 9) Now that the right phis are used for the environments, and we 260 // have potentially revive dead phis in case of a debuggable application, 261 // we can eliminate phis we do not need. Regardless of the debuggable status, 262 // this phase is necessary for statement (b) of the SsaBuilder (see ssa_builder.h), 263 // as well as for the code generation, which does not deal with phis of conflicting 264 // input types. 265 dead_phis.EliminateDeadPhis(); 266 267 // 10) Clear locals. 268 for (HInstructionIterator it(GetGraph()->GetEntryBlock()->GetInstructions()); 269 !it.Done(); 270 it.Advance()) { 271 HInstruction* current = it.Current(); 272 if (current->IsLocal()) { 273 current->GetBlock()->RemoveInstruction(current); 274 } 275 } 276} 277 278HInstruction* SsaBuilder::ValueOfLocal(HBasicBlock* block, size_t local) { 279 return GetLocalsFor(block)->GetInstructionAt(local); 280} 281 282void SsaBuilder::VisitBasicBlock(HBasicBlock* block) { 283 current_locals_ = GetLocalsFor(block); 284 285 if (block->IsLoopHeader()) { 286 // If the block is a loop header, we know we only have visited the pre header 287 // because we are visiting in reverse post order. We create phis for all initialized 288 // locals from the pre header. Their inputs will be populated at the end of 289 // the analysis. 290 for (size_t local = 0; local < current_locals_->Size(); local++) { 291 HInstruction* incoming = ValueOfLocal(block->GetLoopInformation()->GetPreHeader(), local); 292 if (incoming != nullptr) { 293 HPhi* phi = new (GetGraph()->GetArena()) HPhi( 294 GetGraph()->GetArena(), local, 0, Primitive::kPrimVoid); 295 block->AddPhi(phi); 296 current_locals_->SetRawEnvAt(local, phi); 297 } 298 } 299 // Save the loop header so that the last phase of the analysis knows which 300 // blocks need to be updated. 301 loop_headers_.Add(block); 302 } else if (block->GetPredecessors().Size() > 0) { 303 // All predecessors have already been visited because we are visiting in reverse post order. 304 // We merge the values of all locals, creating phis if those values differ. 305 for (size_t local = 0; local < current_locals_->Size(); local++) { 306 bool one_predecessor_has_no_value = false; 307 bool is_different = false; 308 HInstruction* value = ValueOfLocal(block->GetPredecessors().Get(0), local); 309 310 for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) { 311 HInstruction* current = ValueOfLocal(block->GetPredecessors().Get(i), local); 312 if (current == nullptr) { 313 one_predecessor_has_no_value = true; 314 break; 315 } else if (current != value) { 316 is_different = true; 317 } 318 } 319 320 if (one_predecessor_has_no_value) { 321 // If one predecessor has no value for this local, we trust the verifier has 322 // successfully checked that there is a store dominating any read after this block. 323 continue; 324 } 325 326 if (is_different) { 327 HPhi* phi = new (GetGraph()->GetArena()) HPhi( 328 GetGraph()->GetArena(), local, block->GetPredecessors().Size(), Primitive::kPrimVoid); 329 for (size_t i = 0; i < block->GetPredecessors().Size(); i++) { 330 HInstruction* pred_value = ValueOfLocal(block->GetPredecessors().Get(i), local); 331 phi->SetRawInputAt(i, pred_value); 332 } 333 block->AddPhi(phi); 334 value = phi; 335 } 336 current_locals_->SetRawEnvAt(local, value); 337 } 338 } 339 340 // Visit all instructions. The instructions of interest are: 341 // - HLoadLocal: replace them with the current value of the local. 342 // - HStoreLocal: update current value of the local and remove the instruction. 343 // - Instructions that require an environment: populate their environment 344 // with the current values of the locals. 345 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 346 it.Current()->Accept(this); 347 } 348} 349 350/** 351 * Constants in the Dex format are not typed. So the builder types them as 352 * integers, but when doing the SSA form, we might realize the constant 353 * is used for floating point operations. We create a floating-point equivalent 354 * constant to make the operations correctly typed. 355 */ 356HFloatConstant* SsaBuilder::GetFloatEquivalent(HIntConstant* constant) { 357 // We place the floating point constant next to this constant. 358 HFloatConstant* result = constant->GetNext()->AsFloatConstant(); 359 if (result == nullptr) { 360 HGraph* graph = constant->GetBlock()->GetGraph(); 361 ArenaAllocator* allocator = graph->GetArena(); 362 result = new (allocator) HFloatConstant(bit_cast<float, int32_t>(constant->GetValue())); 363 constant->GetBlock()->InsertInstructionBefore(result, constant->GetNext()); 364 } else { 365 // If there is already a constant with the expected type, we know it is 366 // the floating point equivalent of this constant. 367 DCHECK_EQ((bit_cast<int32_t, float>(result->GetValue())), constant->GetValue()); 368 } 369 return result; 370} 371 372/** 373 * Wide constants in the Dex format are not typed. So the builder types them as 374 * longs, but when doing the SSA form, we might realize the constant 375 * is used for floating point operations. We create a floating-point equivalent 376 * constant to make the operations correctly typed. 377 */ 378HDoubleConstant* SsaBuilder::GetDoubleEquivalent(HLongConstant* constant) { 379 // We place the floating point constant next to this constant. 380 HDoubleConstant* result = constant->GetNext()->AsDoubleConstant(); 381 if (result == nullptr) { 382 HGraph* graph = constant->GetBlock()->GetGraph(); 383 ArenaAllocator* allocator = graph->GetArena(); 384 result = new (allocator) HDoubleConstant(bit_cast<double, int64_t>(constant->GetValue())); 385 constant->GetBlock()->InsertInstructionBefore(result, constant->GetNext()); 386 } else { 387 // If there is already a constant with the expected type, we know it is 388 // the floating point equivalent of this constant. 389 DCHECK_EQ((bit_cast<int64_t, double>(result->GetValue())), constant->GetValue()); 390 } 391 return result; 392} 393 394/** 395 * Because of Dex format, we might end up having the same phi being 396 * used for non floating point operations and floating point / reference operations. 397 * Because we want the graph to be correctly typed (and thereafter avoid moves between 398 * floating point registers and core registers), we need to create a copy of the 399 * phi with a floating point / reference type. 400 */ 401HPhi* SsaBuilder::GetFloatDoubleOrReferenceEquivalentOfPhi(HPhi* phi, Primitive::Type type) { 402 // We place the floating point /reference phi next to this phi. 403 HInstruction* next = phi->GetNext(); 404 if (next != nullptr 405 && next->AsPhi()->GetRegNumber() == phi->GetRegNumber() 406 && next->GetType() != type) { 407 // Move to the next phi to see if it is the one we are looking for. 408 next = next->GetNext(); 409 } 410 411 if (next == nullptr 412 || (next->AsPhi()->GetRegNumber() != phi->GetRegNumber()) 413 || (next->GetType() != type)) { 414 ArenaAllocator* allocator = phi->GetBlock()->GetGraph()->GetArena(); 415 HPhi* new_phi = new (allocator) HPhi(allocator, phi->GetRegNumber(), phi->InputCount(), type); 416 for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { 417 // Copy the inputs. Note that the graph may not be correctly typed by doing this copy, 418 // but the type propagation phase will fix it. 419 new_phi->SetRawInputAt(i, phi->InputAt(i)); 420 } 421 phi->GetBlock()->InsertPhiAfter(new_phi, phi); 422 return new_phi; 423 } else { 424 DCHECK_EQ(next->GetType(), type); 425 return next->AsPhi(); 426 } 427} 428 429HInstruction* SsaBuilder::GetFloatOrDoubleEquivalent(HInstruction* user, 430 HInstruction* value, 431 Primitive::Type type) { 432 if (value->IsArrayGet()) { 433 // The verifier has checked that values in arrays cannot be used for both 434 // floating point and non-floating point operations. It is therefore safe to just 435 // change the type of the operation. 436 value->AsArrayGet()->SetType(type); 437 return value; 438 } else if (value->IsLongConstant()) { 439 return GetDoubleEquivalent(value->AsLongConstant()); 440 } else if (value->IsIntConstant()) { 441 return GetFloatEquivalent(value->AsIntConstant()); 442 } else if (value->IsPhi()) { 443 return GetFloatDoubleOrReferenceEquivalentOfPhi(value->AsPhi(), type); 444 } else { 445 // For other instructions, we assume the verifier has checked that the dex format is correctly 446 // typed and the value in a dex register will not be used for both floating point and 447 // non-floating point operations. So the only reason an instruction would want a floating 448 // point equivalent is for an unused phi that will be removed by the dead phi elimination phase. 449 DCHECK(user->IsPhi()); 450 return value; 451 } 452} 453 454HInstruction* SsaBuilder::GetReferenceTypeEquivalent(HInstruction* value) { 455 if (value->IsIntConstant() && value->AsIntConstant()->GetValue() == 0) { 456 return value->GetBlock()->GetGraph()->GetNullConstant(); 457 } else if (value->IsPhi()) { 458 return GetFloatDoubleOrReferenceEquivalentOfPhi(value->AsPhi(), Primitive::kPrimNot); 459 } else { 460 return nullptr; 461 } 462} 463 464void SsaBuilder::VisitLoadLocal(HLoadLocal* load) { 465 HInstruction* value = current_locals_->GetInstructionAt(load->GetLocal()->GetRegNumber()); 466 // If the operation requests a specific type, we make sure its input is of that type. 467 if (load->GetType() != value->GetType()) { 468 if (load->GetType() == Primitive::kPrimFloat || load->GetType() == Primitive::kPrimDouble) { 469 value = GetFloatOrDoubleEquivalent(load, value, load->GetType()); 470 } else if (load->GetType() == Primitive::kPrimNot) { 471 value = GetReferenceTypeEquivalent(value); 472 } 473 } 474 load->ReplaceWith(value); 475 load->GetBlock()->RemoveInstruction(load); 476} 477 478void SsaBuilder::VisitStoreLocal(HStoreLocal* store) { 479 current_locals_->SetRawEnvAt(store->GetLocal()->GetRegNumber(), store->InputAt(1)); 480 store->GetBlock()->RemoveInstruction(store); 481} 482 483void SsaBuilder::VisitInstruction(HInstruction* instruction) { 484 if (!instruction->NeedsEnvironment()) { 485 return; 486 } 487 HEnvironment* environment = new (GetGraph()->GetArena()) HEnvironment( 488 GetGraph()->GetArena(), current_locals_->Size()); 489 environment->CopyFrom(current_locals_); 490 instruction->SetEnvironment(environment); 491} 492 493void SsaBuilder::VisitTemporary(HTemporary* temp) { 494 // Temporaries are only used by the baseline register allocator. 495 temp->GetBlock()->RemoveInstruction(temp); 496} 497 498} // namespace art 499