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 "dead_code_elimination.h" 18 19 #include "base/array_ref.h" 20 #include "base/bit_vector-inl.h" 21 #include "base/scoped_arena_allocator.h" 22 #include "base/scoped_arena_containers.h" 23 #include "base/stl_util.h" 24 #include "ssa_phi_elimination.h" 25 26 namespace art { 27 28 static void MarkReachableBlocks(HGraph* graph, ArenaBitVector* visited) { 29 // Use local allocator for allocating memory. 30 ScopedArenaAllocator allocator(graph->GetArenaStack()); 31 32 ScopedArenaVector<HBasicBlock*> worklist(allocator.Adapter(kArenaAllocDCE)); 33 constexpr size_t kDefaultWorlistSize = 8; 34 worklist.reserve(kDefaultWorlistSize); 35 visited->SetBit(graph->GetEntryBlock()->GetBlockId()); 36 worklist.push_back(graph->GetEntryBlock()); 37 38 while (!worklist.empty()) { 39 HBasicBlock* block = worklist.back(); 40 worklist.pop_back(); 41 int block_id = block->GetBlockId(); 42 DCHECK(visited->IsBitSet(block_id)); 43 44 ArrayRef<HBasicBlock* const> live_successors(block->GetSuccessors()); 45 HInstruction* last_instruction = block->GetLastInstruction(); 46 if (last_instruction->IsIf()) { 47 HIf* if_instruction = last_instruction->AsIf(); 48 HInstruction* condition = if_instruction->InputAt(0); 49 if (condition->IsIntConstant()) { 50 if (condition->AsIntConstant()->IsTrue()) { 51 live_successors = live_successors.SubArray(0u, 1u); 52 DCHECK_EQ(live_successors[0], if_instruction->IfTrueSuccessor()); 53 } else { 54 DCHECK(condition->AsIntConstant()->IsFalse()) << condition->AsIntConstant()->GetValue(); 55 live_successors = live_successors.SubArray(1u, 1u); 56 DCHECK_EQ(live_successors[0], if_instruction->IfFalseSuccessor()); 57 } 58 } 59 } else if (last_instruction->IsPackedSwitch()) { 60 HPackedSwitch* switch_instruction = last_instruction->AsPackedSwitch(); 61 HInstruction* switch_input = switch_instruction->InputAt(0); 62 if (switch_input->IsIntConstant()) { 63 int32_t switch_value = switch_input->AsIntConstant()->GetValue(); 64 int32_t start_value = switch_instruction->GetStartValue(); 65 // Note: Though the spec forbids packed-switch values to wrap around, we leave 66 // that task to the verifier and use unsigned arithmetic with it's "modulo 2^32" 67 // semantics to check if the value is in range, wrapped or not. 68 uint32_t switch_index = 69 static_cast<uint32_t>(switch_value) - static_cast<uint32_t>(start_value); 70 if (switch_index < switch_instruction->GetNumEntries()) { 71 live_successors = live_successors.SubArray(switch_index, 1u); 72 DCHECK_EQ(live_successors[0], block->GetSuccessors()[switch_index]); 73 } else { 74 live_successors = live_successors.SubArray(switch_instruction->GetNumEntries(), 1u); 75 DCHECK_EQ(live_successors[0], switch_instruction->GetDefaultBlock()); 76 } 77 } 78 } 79 80 for (HBasicBlock* successor : live_successors) { 81 // Add only those successors that have not been visited yet. 82 if (!visited->IsBitSet(successor->GetBlockId())) { 83 visited->SetBit(successor->GetBlockId()); 84 worklist.push_back(successor); 85 } 86 } 87 } 88 } 89 90 void HDeadCodeElimination::MaybeRecordDeadBlock(HBasicBlock* block) { 91 if (stats_ != nullptr) { 92 stats_->RecordStat(MethodCompilationStat::kRemovedDeadInstruction, 93 block->GetPhis().CountSize() + block->GetInstructions().CountSize()); 94 } 95 } 96 97 void HDeadCodeElimination::MaybeRecordSimplifyIf() { 98 if (stats_ != nullptr) { 99 stats_->RecordStat(MethodCompilationStat::kSimplifyIf); 100 } 101 } 102 103 static bool HasInput(HCondition* instruction, HInstruction* input) { 104 return (instruction->InputAt(0) == input) || 105 (instruction->InputAt(1) == input); 106 } 107 108 static bool HasEquality(IfCondition condition) { 109 switch (condition) { 110 case kCondEQ: 111 case kCondLE: 112 case kCondGE: 113 case kCondBE: 114 case kCondAE: 115 return true; 116 case kCondNE: 117 case kCondLT: 118 case kCondGT: 119 case kCondB: 120 case kCondA: 121 return false; 122 } 123 } 124 125 static HConstant* Evaluate(HCondition* condition, HInstruction* left, HInstruction* right) { 126 if (left == right && !DataType::IsFloatingPointType(left->GetType())) { 127 return condition->GetBlock()->GetGraph()->GetIntConstant( 128 HasEquality(condition->GetCondition()) ? 1 : 0); 129 } 130 131 if (!left->IsConstant() || !right->IsConstant()) { 132 return nullptr; 133 } 134 135 if (left->IsIntConstant()) { 136 return condition->Evaluate(left->AsIntConstant(), right->AsIntConstant()); 137 } else if (left->IsNullConstant()) { 138 return condition->Evaluate(left->AsNullConstant(), right->AsNullConstant()); 139 } else if (left->IsLongConstant()) { 140 return condition->Evaluate(left->AsLongConstant(), right->AsLongConstant()); 141 } else if (left->IsFloatConstant()) { 142 return condition->Evaluate(left->AsFloatConstant(), right->AsFloatConstant()); 143 } else { 144 DCHECK(left->IsDoubleConstant()); 145 return condition->Evaluate(left->AsDoubleConstant(), right->AsDoubleConstant()); 146 } 147 } 148 149 static bool RemoveNonNullControlDependences(HBasicBlock* block, HBasicBlock* throws) { 150 // Test for an if as last statement. 151 if (!block->EndsWithIf()) { 152 return false; 153 } 154 HIf* ifs = block->GetLastInstruction()->AsIf(); 155 // Find either: 156 // if obj == null 157 // throws 158 // else 159 // not_throws 160 // or: 161 // if obj != null 162 // not_throws 163 // else 164 // throws 165 HInstruction* cond = ifs->InputAt(0); 166 HBasicBlock* not_throws = nullptr; 167 if (throws == ifs->IfTrueSuccessor() && cond->IsEqual()) { 168 not_throws = ifs->IfFalseSuccessor(); 169 } else if (throws == ifs->IfFalseSuccessor() && cond->IsNotEqual()) { 170 not_throws = ifs->IfTrueSuccessor(); 171 } else { 172 return false; 173 } 174 DCHECK(cond->IsEqual() || cond->IsNotEqual()); 175 HInstruction* obj = cond->InputAt(1); 176 if (obj->IsNullConstant()) { 177 obj = cond->InputAt(0); 178 } else if (!cond->InputAt(0)->IsNullConstant()) { 179 return false; 180 } 181 // Scan all uses of obj and find null check under control dependence. 182 HBoundType* bound = nullptr; 183 const HUseList<HInstruction*>& uses = obj->GetUses(); 184 for (auto it = uses.begin(), end = uses.end(); it != end;) { 185 HInstruction* user = it->GetUser(); 186 ++it; // increment before possibly replacing 187 if (user->IsNullCheck()) { 188 HBasicBlock* user_block = user->GetBlock(); 189 if (user_block != block && 190 user_block != throws && 191 block->Dominates(user_block)) { 192 if (bound == nullptr) { 193 ReferenceTypeInfo ti = obj->GetReferenceTypeInfo(); 194 bound = new (obj->GetBlock()->GetGraph()->GetAllocator()) HBoundType(obj); 195 bound->SetUpperBound(ti, /*can_be_null*/ false); 196 bound->SetReferenceTypeInfo(ti); 197 bound->SetCanBeNull(false); 198 not_throws->InsertInstructionBefore(bound, not_throws->GetFirstInstruction()); 199 } 200 user->ReplaceWith(bound); 201 user_block->RemoveInstruction(user); 202 } 203 } 204 } 205 return bound != nullptr; 206 } 207 208 // Simplify the pattern: 209 // 210 // B1 211 // / \ 212 // | foo() // always throws 213 // \ goto B2 214 // \ / 215 // B2 216 // 217 // Into: 218 // 219 // B1 220 // / \ 221 // | foo() 222 // | goto Exit 223 // | | 224 // B2 Exit 225 // 226 // Rationale: 227 // Removal of the never taken edge to B2 may expose 228 // other optimization opportunities, such as code sinking. 229 bool HDeadCodeElimination::SimplifyAlwaysThrows() { 230 // Make sure exceptions go to exit. 231 if (graph_->HasTryCatch()) { 232 return false; 233 } 234 HBasicBlock* exit = graph_->GetExitBlock(); 235 if (exit == nullptr) { 236 return false; 237 } 238 239 bool rerun_dominance_and_loop_analysis = false; 240 241 // Order does not matter, just pick one. 242 for (HBasicBlock* block : graph_->GetReversePostOrder()) { 243 HInstruction* first = block->GetFirstInstruction(); 244 HInstruction* last = block->GetLastInstruction(); 245 // Ensure only one throwing instruction appears before goto. 246 if (first->AlwaysThrows() && 247 first->GetNext() == last && 248 last->IsGoto() && 249 block->GetPhis().IsEmpty() && 250 block->GetPredecessors().size() == 1u) { 251 DCHECK_EQ(block->GetSuccessors().size(), 1u); 252 HBasicBlock* pred = block->GetSinglePredecessor(); 253 HBasicBlock* succ = block->GetSingleSuccessor(); 254 // Ensure no computations are merged through throwing block. 255 // This does not prevent the optimization per se, but would 256 // require an elaborate clean up of the SSA graph. 257 if (succ != exit && 258 !block->Dominates(pred) && 259 pred->Dominates(succ) && 260 succ->GetPredecessors().size() > 1u && 261 succ->GetPhis().IsEmpty()) { 262 block->ReplaceSuccessor(succ, exit); 263 rerun_dominance_and_loop_analysis = true; 264 MaybeRecordStat(stats_, MethodCompilationStat::kSimplifyThrowingInvoke); 265 // Perform a quick follow up optimization on object != null control dependences 266 // that is much cheaper to perform now than in a later phase. 267 if (RemoveNonNullControlDependences(pred, block)) { 268 MaybeRecordStat(stats_, MethodCompilationStat::kRemovedNullCheck); 269 } 270 } 271 } 272 } 273 274 // We need to re-analyze the graph in order to run DCE afterwards. 275 if (rerun_dominance_and_loop_analysis) { 276 graph_->ClearLoopInformation(); 277 graph_->ClearDominanceInformation(); 278 graph_->BuildDominatorTree(); 279 return true; 280 } 281 return false; 282 } 283 284 // Simplify the pattern: 285 // 286 // B1 B2 ... 287 // goto goto goto 288 // \ | / 289 // \ | / 290 // B3 291 // i1 = phi(input, input) 292 // (i2 = condition on i1) 293 // if i1 (or i2) 294 // / \ 295 // / \ 296 // B4 B5 297 // 298 // Into: 299 // 300 // B1 B2 ... 301 // | | | 302 // B4 B5 B? 303 // 304 // Note that individual edges can be redirected (for example B2->B3 305 // can be redirected as B2->B5) without applying this optimization 306 // to other incoming edges. 307 // 308 // This simplification cannot be applied to catch blocks, because 309 // exception handler edges do not represent normal control flow. 310 // Though in theory this could still apply to normal control flow 311 // going directly to a catch block, we cannot support it at the 312 // moment because the catch Phi's inputs do not correspond to the 313 // catch block's predecessors, so we cannot identify which 314 // predecessor corresponds to a given statically evaluated input. 315 // 316 // We do not apply this optimization to loop headers as this could 317 // create irreducible loops. We rely on the suspend check in the 318 // loop header to prevent the pattern match. 319 // 320 // Note that we rely on the dead code elimination to get rid of B3. 321 bool HDeadCodeElimination::SimplifyIfs() { 322 bool simplified_one_or_more_ifs = false; 323 bool rerun_dominance_and_loop_analysis = false; 324 325 for (HBasicBlock* block : graph_->GetReversePostOrder()) { 326 HInstruction* last = block->GetLastInstruction(); 327 HInstruction* first = block->GetFirstInstruction(); 328 if (!block->IsCatchBlock() && 329 last->IsIf() && 330 block->HasSinglePhi() && 331 block->GetFirstPhi()->HasOnlyOneNonEnvironmentUse()) { 332 bool has_only_phi_and_if = (last == first) && (last->InputAt(0) == block->GetFirstPhi()); 333 bool has_only_phi_condition_and_if = 334 !has_only_phi_and_if && 335 first->IsCondition() && 336 HasInput(first->AsCondition(), block->GetFirstPhi()) && 337 (first->GetNext() == last) && 338 (last->InputAt(0) == first) && 339 first->HasOnlyOneNonEnvironmentUse(); 340 341 if (has_only_phi_and_if || has_only_phi_condition_and_if) { 342 DCHECK(!block->IsLoopHeader()); 343 HPhi* phi = block->GetFirstPhi()->AsPhi(); 344 bool phi_input_is_left = (first->InputAt(0) == phi); 345 346 // Walk over all inputs of the phis and update the control flow of 347 // predecessors feeding constants to the phi. 348 // Note that phi->InputCount() may change inside the loop. 349 for (size_t i = 0; i < phi->InputCount();) { 350 HInstruction* input = phi->InputAt(i); 351 HInstruction* value_to_check = nullptr; 352 if (has_only_phi_and_if) { 353 if (input->IsIntConstant()) { 354 value_to_check = input; 355 } 356 } else { 357 DCHECK(has_only_phi_condition_and_if); 358 if (phi_input_is_left) { 359 value_to_check = Evaluate(first->AsCondition(), input, first->InputAt(1)); 360 } else { 361 value_to_check = Evaluate(first->AsCondition(), first->InputAt(0), input); 362 } 363 } 364 if (value_to_check == nullptr) { 365 // Could not evaluate to a constant, continue iterating over the inputs. 366 ++i; 367 } else { 368 HBasicBlock* predecessor_to_update = block->GetPredecessors()[i]; 369 HBasicBlock* successor_to_update = nullptr; 370 if (value_to_check->AsIntConstant()->IsTrue()) { 371 successor_to_update = last->AsIf()->IfTrueSuccessor(); 372 } else { 373 DCHECK(value_to_check->AsIntConstant()->IsFalse()) 374 << value_to_check->AsIntConstant()->GetValue(); 375 successor_to_update = last->AsIf()->IfFalseSuccessor(); 376 } 377 predecessor_to_update->ReplaceSuccessor(block, successor_to_update); 378 phi->RemoveInputAt(i); 379 simplified_one_or_more_ifs = true; 380 if (block->IsInLoop()) { 381 rerun_dominance_and_loop_analysis = true; 382 } 383 // For simplicity, don't create a dead block, let the dead code elimination 384 // pass deal with it. 385 if (phi->InputCount() == 1) { 386 break; 387 } 388 } 389 } 390 if (block->GetPredecessors().size() == 1) { 391 phi->ReplaceWith(phi->InputAt(0)); 392 block->RemovePhi(phi); 393 if (has_only_phi_condition_and_if) { 394 // Evaluate here (and not wait for a constant folding pass) to open 395 // more opportunities for DCE. 396 HInstruction* result = first->AsCondition()->TryStaticEvaluation(); 397 if (result != nullptr) { 398 first->ReplaceWith(result); 399 block->RemoveInstruction(first); 400 } 401 } 402 } 403 if (simplified_one_or_more_ifs) { 404 MaybeRecordSimplifyIf(); 405 } 406 } 407 } 408 } 409 // We need to re-analyze the graph in order to run DCE afterwards. 410 if (simplified_one_or_more_ifs) { 411 if (rerun_dominance_and_loop_analysis) { 412 graph_->ClearLoopInformation(); 413 graph_->ClearDominanceInformation(); 414 graph_->BuildDominatorTree(); 415 } else { 416 graph_->ClearDominanceInformation(); 417 // We have introduced critical edges, remove them. 418 graph_->SimplifyCFG(); 419 graph_->ComputeDominanceInformation(); 420 graph_->ComputeTryBlockInformation(); 421 } 422 } 423 424 return simplified_one_or_more_ifs; 425 } 426 427 void HDeadCodeElimination::ConnectSuccessiveBlocks() { 428 // Order does not matter. Skip the entry block by starting at index 1 in reverse post order. 429 for (size_t i = 1u, size = graph_->GetReversePostOrder().size(); i != size; ++i) { 430 HBasicBlock* block = graph_->GetReversePostOrder()[i]; 431 DCHECK(!block->IsEntryBlock()); 432 while (block->GetLastInstruction()->IsGoto()) { 433 HBasicBlock* successor = block->GetSingleSuccessor(); 434 if (successor->IsExitBlock() || successor->GetPredecessors().size() != 1u) { 435 break; 436 } 437 DCHECK_LT(i, IndexOfElement(graph_->GetReversePostOrder(), successor)); 438 block->MergeWith(successor); 439 --size; 440 DCHECK_EQ(size, graph_->GetReversePostOrder().size()); 441 DCHECK_EQ(block, graph_->GetReversePostOrder()[i]); 442 // Reiterate on this block in case it can be merged with its new successor. 443 } 444 } 445 } 446 447 bool HDeadCodeElimination::RemoveDeadBlocks() { 448 // Use local allocator for allocating memory. 449 ScopedArenaAllocator allocator(graph_->GetArenaStack()); 450 451 // Classify blocks as reachable/unreachable. 452 ArenaBitVector live_blocks(&allocator, graph_->GetBlocks().size(), false, kArenaAllocDCE); 453 live_blocks.ClearAllBits(); 454 455 MarkReachableBlocks(graph_, &live_blocks); 456 bool removed_one_or_more_blocks = false; 457 bool rerun_dominance_and_loop_analysis = false; 458 459 // Remove all dead blocks. Iterate in post order because removal needs the 460 // block's chain of dominators and nested loops need to be updated from the 461 // inside out. 462 for (HBasicBlock* block : graph_->GetPostOrder()) { 463 int id = block->GetBlockId(); 464 if (!live_blocks.IsBitSet(id)) { 465 MaybeRecordDeadBlock(block); 466 block->DisconnectAndDelete(); 467 removed_one_or_more_blocks = true; 468 if (block->IsInLoop()) { 469 rerun_dominance_and_loop_analysis = true; 470 } 471 } 472 } 473 474 // If we removed at least one block, we need to recompute the full 475 // dominator tree and try block membership. 476 if (removed_one_or_more_blocks) { 477 if (rerun_dominance_and_loop_analysis) { 478 graph_->ClearLoopInformation(); 479 graph_->ClearDominanceInformation(); 480 graph_->BuildDominatorTree(); 481 } else { 482 graph_->ClearDominanceInformation(); 483 graph_->ComputeDominanceInformation(); 484 graph_->ComputeTryBlockInformation(); 485 } 486 } 487 return removed_one_or_more_blocks; 488 } 489 490 void HDeadCodeElimination::RemoveDeadInstructions() { 491 // Process basic blocks in post-order in the dominator tree, so that 492 // a dead instruction depending on another dead instruction is removed. 493 for (HBasicBlock* block : graph_->GetPostOrder()) { 494 // Traverse this block's instructions in backward order and remove 495 // the unused ones. 496 HBackwardInstructionIterator i(block->GetInstructions()); 497 // Skip the first iteration, as the last instruction of a block is 498 // a branching instruction. 499 DCHECK(i.Current()->IsControlFlow()); 500 for (i.Advance(); !i.Done(); i.Advance()) { 501 HInstruction* inst = i.Current(); 502 DCHECK(!inst->IsControlFlow()); 503 if (inst->IsDeadAndRemovable()) { 504 block->RemoveInstruction(inst); 505 MaybeRecordStat(stats_, MethodCompilationStat::kRemovedDeadInstruction); 506 } 507 } 508 } 509 } 510 511 void HDeadCodeElimination::Run() { 512 // Do not eliminate dead blocks if the graph has irreducible loops. We could 513 // support it, but that would require changes in our loop representation to handle 514 // multiple entry points. We decided it was not worth the complexity. 515 if (!graph_->HasIrreducibleLoops()) { 516 // Simplify graph to generate more dead block patterns. 517 ConnectSuccessiveBlocks(); 518 bool did_any_simplification = false; 519 did_any_simplification |= SimplifyAlwaysThrows(); 520 did_any_simplification |= SimplifyIfs(); 521 did_any_simplification |= RemoveDeadBlocks(); 522 if (did_any_simplification) { 523 // Connect successive blocks created by dead branches. 524 ConnectSuccessiveBlocks(); 525 } 526 } 527 SsaRedundantPhiElimination(graph_).Run(); 528 RemoveDeadInstructions(); 529 } 530 531 } // namespace art 532