Roland Levillain | 72bceff | 2014-09-15 18:29:00 +0100 | [diff] [blame] | 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 | |
David Brazdil | d9c9037 | 2016-09-14 16:53:55 +0100 | [diff] [blame] | 19 | #include "base/array_ref.h" |
Roland Levillain | 72bceff | 2014-09-15 18:29:00 +0100 | [diff] [blame] | 20 | #include "base/bit_vector-inl.h" |
Vladimir Marko | 009d166 | 2017-10-10 13:21:15 +0100 | [diff] [blame] | 21 | #include "base/scoped_arena_allocator.h" |
| 22 | #include "base/scoped_arena_containers.h" |
Vladimir Marko | 2c45bc9 | 2016-10-25 16:54:12 +0100 | [diff] [blame] | 23 | #include "base/stl_util.h" |
David Brazdil | 84daae5 | 2015-05-18 12:06:52 +0100 | [diff] [blame] | 24 | #include "ssa_phi_elimination.h" |
Roland Levillain | 72bceff | 2014-09-15 18:29:00 +0100 | [diff] [blame] | 25 | |
| 26 | namespace art { |
| 27 | |
Vladimir Marko | 211c211 | 2015-09-24 16:52:33 +0100 | [diff] [blame] | 28 | static void MarkReachableBlocks(HGraph* graph, ArenaBitVector* visited) { |
Vladimir Marko | 009d166 | 2017-10-10 13:21:15 +0100 | [diff] [blame] | 29 | // Use local allocator for allocating memory. |
| 30 | ScopedArenaAllocator allocator(graph->GetArenaStack()); |
| 31 | |
| 32 | ScopedArenaVector<HBasicBlock*> worklist(allocator.Adapter(kArenaAllocDCE)); |
Vladimir Marko | 211c211 | 2015-09-24 16:52:33 +0100 | [diff] [blame] | 33 | constexpr size_t kDefaultWorlistSize = 8; |
| 34 | worklist.reserve(kDefaultWorlistSize); |
| 35 | visited->SetBit(graph->GetEntryBlock()->GetBlockId()); |
| 36 | worklist.push_back(graph->GetEntryBlock()); |
David Brazdil | 2d7352b | 2015-04-20 14:52:42 +0100 | [diff] [blame] | 37 | |
Vladimir Marko | 211c211 | 2015-09-24 16:52:33 +0100 | [diff] [blame] | 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()) { |
Roland Levillain | 1a65388 | 2016-03-18 18:05:57 +0000 | [diff] [blame] | 50 | if (condition->AsIntConstant()->IsTrue()) { |
Vladimir Marko | 211c211 | 2015-09-24 16:52:33 +0100 | [diff] [blame] | 51 | live_successors = live_successors.SubArray(0u, 1u); |
| 52 | DCHECK_EQ(live_successors[0], if_instruction->IfTrueSuccessor()); |
| 53 | } else { |
Roland Levillain | 1a65388 | 2016-03-18 18:05:57 +0000 | [diff] [blame] | 54 | DCHECK(condition->AsIntConstant()->IsFalse()) << condition->AsIntConstant()->GetValue(); |
Vladimir Marko | 211c211 | 2015-09-24 16:52:33 +0100 | [diff] [blame] | 55 | live_successors = live_successors.SubArray(1u, 1u); |
| 56 | DCHECK_EQ(live_successors[0], if_instruction->IfFalseSuccessor()); |
| 57 | } |
Mark Mendell | fe57faa | 2015-09-18 09:26:15 -0400 | [diff] [blame] | 58 | } |
Vladimir Marko | 211c211 | 2015-09-24 16:52:33 +0100 | [diff] [blame] | 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(); |
Vladimir Marko | 430c4f5 | 2015-09-25 17:10:15 +0100 | [diff] [blame] | 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); |
Vladimir Marko | 211c211 | 2015-09-24 16:52:33 +0100 | [diff] [blame] | 70 | if (switch_index < switch_instruction->GetNumEntries()) { |
| 71 | live_successors = live_successors.SubArray(switch_index, 1u); |
Vladimir Marko | ec7802a | 2015-10-01 20:57:57 +0100 | [diff] [blame] | 72 | DCHECK_EQ(live_successors[0], block->GetSuccessors()[switch_index]); |
Vladimir Marko | 211c211 | 2015-09-24 16:52:33 +0100 | [diff] [blame] | 73 | } else { |
| 74 | live_successors = live_successors.SubArray(switch_instruction->GetNumEntries(), 1u); |
| 75 | DCHECK_EQ(live_successors[0], switch_instruction->GetDefaultBlock()); |
| 76 | } |
Mark Mendell | fe57faa | 2015-09-18 09:26:15 -0400 | [diff] [blame] | 77 | } |
| 78 | } |
Vladimir Marko | 211c211 | 2015-09-24 16:52:33 +0100 | [diff] [blame] | 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 | } |
David Brazdil | 2d7352b | 2015-04-20 14:52:42 +0100 | [diff] [blame] | 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 | |
Nicolas Geoffray | dac9b19 | 2016-07-15 10:46:17 +0100 | [diff] [blame] | 97 | void HDeadCodeElimination::MaybeRecordSimplifyIf() { |
| 98 | if (stats_ != nullptr) { |
| 99 | stats_->RecordStat(MethodCompilationStat::kSimplifyIf); |
Nicolas Geoffray | 09aa147 | 2016-01-19 10:52:54 +0000 | [diff] [blame] | 100 | } |
Nicolas Geoffray | dac9b19 | 2016-07-15 10:46:17 +0100 | [diff] [blame] | 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) { |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 126 | if (left == right && !DataType::IsFloatingPointType(left->GetType())) { |
Nicolas Geoffray | dac9b19 | 2016-07-15 10:46:17 +0100 | [diff] [blame] | 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 | |
Aart Bik | 4c563ca | 2018-01-24 16:34:25 -0800 | [diff] [blame] | 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 | |
Nicolas Geoffray | dac9b19 | 2016-07-15 10:46:17 +0100 | [diff] [blame] | 208 | // Simplify the pattern: |
| 209 | // |
Aart Bik | a8b8e9b | 2018-01-09 11:01:02 -0800 | [diff] [blame] | 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); |
Aart Bik | 4c563ca | 2018-01-24 16:34:25 -0800 | [diff] [blame] | 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 | } |
Aart Bik | a8b8e9b | 2018-01-09 11:01:02 -0800 | [diff] [blame] | 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 | // |
Nicolas Geoffray | dac9b19 | 2016-07-15 10:46:17 +0100 | [diff] [blame] | 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 | // |
Vladimir Marko | 606c8f0 | 2016-11-03 13:01:28 +0000 | [diff] [blame] | 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. |
Nicolas Geoffray | dac9b19 | 2016-07-15 10:46:17 +0100 | [diff] [blame] | 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 | |
Vladimir Marko | 2c45bc9 | 2016-10-25 16:54:12 +0100 | [diff] [blame] | 325 | for (HBasicBlock* block : graph_->GetReversePostOrder()) { |
Nicolas Geoffray | dac9b19 | 2016-07-15 10:46:17 +0100 | [diff] [blame] | 326 | HInstruction* last = block->GetLastInstruction(); |
| 327 | HInstruction* first = block->GetFirstInstruction(); |
Vladimir Marko | 606c8f0 | 2016-11-03 13:01:28 +0000 | [diff] [blame] | 328 | if (!block->IsCatchBlock() && |
| 329 | last->IsIf() && |
Nicolas Geoffray | dac9b19 | 2016-07-15 10:46:17 +0100 | [diff] [blame] | 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() { |
Vladimir Marko | 2c45bc9 | 2016-10-25 16:54:12 +0100 | [diff] [blame] | 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. |
Nicolas Geoffray | dac9b19 | 2016-07-15 10:46:17 +0100 | [diff] [blame] | 443 | } |
Nicolas Geoffray | dac9b19 | 2016-07-15 10:46:17 +0100 | [diff] [blame] | 444 | } |
| 445 | } |
| 446 | |
| 447 | bool HDeadCodeElimination::RemoveDeadBlocks() { |
Vladimir Marko | 009d166 | 2017-10-10 13:21:15 +0100 | [diff] [blame] | 448 | // Use local allocator for allocating memory. |
| 449 | ScopedArenaAllocator allocator(graph_->GetArenaStack()); |
| 450 | |
David Brazdil | 2d7352b | 2015-04-20 14:52:42 +0100 | [diff] [blame] | 451 | // Classify blocks as reachable/unreachable. |
Vladimir Marko | 009d166 | 2017-10-10 13:21:15 +0100 | [diff] [blame] | 452 | ArenaBitVector live_blocks(&allocator, graph_->GetBlocks().size(), false, kArenaAllocDCE); |
| 453 | live_blocks.ClearAllBits(); |
David Brazdil | a4b8c21 | 2015-05-07 09:59:30 +0100 | [diff] [blame] | 454 | |
Vladimir Marko | 211c211 | 2015-09-24 16:52:33 +0100 | [diff] [blame] | 455 | MarkReachableBlocks(graph_, &live_blocks); |
Nicolas Geoffray | 1f82ecc | 2015-06-24 12:20:24 +0100 | [diff] [blame] | 456 | bool removed_one_or_more_blocks = false; |
Nicolas Geoffray | 15bd228 | 2016-01-05 15:55:41 +0000 | [diff] [blame] | 457 | bool rerun_dominance_and_loop_analysis = false; |
David Brazdil | 2d7352b | 2015-04-20 14:52:42 +0100 | [diff] [blame] | 458 | |
David Brazdil | a4b8c21 | 2015-05-07 09:59:30 +0100 | [diff] [blame] | 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. |
Vladimir Marko | 2c45bc9 | 2016-10-25 16:54:12 +0100 | [diff] [blame] | 462 | for (HBasicBlock* block : graph_->GetPostOrder()) { |
David Brazdil | a4b8c21 | 2015-05-07 09:59:30 +0100 | [diff] [blame] | 463 | int id = block->GetBlockId(); |
Nicolas Geoffray | 15bd228 | 2016-01-05 15:55:41 +0000 | [diff] [blame] | 464 | if (!live_blocks.IsBitSet(id)) { |
David Brazdil | 69a2804 | 2015-04-29 17:16:07 +0100 | [diff] [blame] | 465 | MaybeRecordDeadBlock(block); |
| 466 | block->DisconnectAndDelete(); |
Nicolas Geoffray | 1f82ecc | 2015-06-24 12:20:24 +0100 | [diff] [blame] | 467 | removed_one_or_more_blocks = true; |
Nicolas Geoffray | 15bd228 | 2016-01-05 15:55:41 +0000 | [diff] [blame] | 468 | if (block->IsInLoop()) { |
| 469 | rerun_dominance_and_loop_analysis = true; |
| 470 | } |
David Brazdil | 2d7352b | 2015-04-20 14:52:42 +0100 | [diff] [blame] | 471 | } |
David Brazdil | 2d7352b | 2015-04-20 14:52:42 +0100 | [diff] [blame] | 472 | } |
| 473 | |
Nicolas Geoffray | 1f82ecc | 2015-06-24 12:20:24 +0100 | [diff] [blame] | 474 | // If we removed at least one block, we need to recompute the full |
David Brazdil | 8a7c0fe | 2015-11-02 20:24:55 +0000 | [diff] [blame] | 475 | // dominator tree and try block membership. |
Nicolas Geoffray | 1f82ecc | 2015-06-24 12:20:24 +0100 | [diff] [blame] | 476 | if (removed_one_or_more_blocks) { |
Nicolas Geoffray | 15bd228 | 2016-01-05 15:55:41 +0000 | [diff] [blame] | 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 | } |
Nicolas Geoffray | 1f82ecc | 2015-06-24 12:20:24 +0100 | [diff] [blame] | 486 | } |
Nicolas Geoffray | dac9b19 | 2016-07-15 10:46:17 +0100 | [diff] [blame] | 487 | return removed_one_or_more_blocks; |
David Brazdil | 2d7352b | 2015-04-20 14:52:42 +0100 | [diff] [blame] | 488 | } |
| 489 | |
| 490 | void HDeadCodeElimination::RemoveDeadInstructions() { |
Roland Levillain | 72bceff | 2014-09-15 18:29:00 +0100 | [diff] [blame] | 491 | // Process basic blocks in post-order in the dominator tree, so that |
David Brazdil | 2d7352b | 2015-04-20 14:52:42 +0100 | [diff] [blame] | 492 | // a dead instruction depending on another dead instruction is removed. |
Vladimir Marko | 2c45bc9 | 2016-10-25 16:54:12 +0100 | [diff] [blame] | 493 | for (HBasicBlock* block : graph_->GetPostOrder()) { |
Roland Levillain | 72bceff | 2014-09-15 18:29:00 +0100 | [diff] [blame] | 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()); |
Aart Bik | 482095d | 2016-10-10 15:39:10 -0700 | [diff] [blame] | 503 | if (inst->IsDeadAndRemovable()) { |
Roland Levillain | 72bceff | 2014-09-15 18:29:00 +0100 | [diff] [blame] | 504 | block->RemoveInstruction(inst); |
Igor Murashkin | 1e065a5 | 2017-08-09 13:20:34 -0700 | [diff] [blame] | 505 | MaybeRecordStat(stats_, MethodCompilationStat::kRemovedDeadInstruction); |
Roland Levillain | 72bceff | 2014-09-15 18:29:00 +0100 | [diff] [blame] | 506 | } |
| 507 | } |
| 508 | } |
| 509 | } |
| 510 | |
Aart Bik | 2477320 | 2018-04-26 10:28:51 -0700 | [diff] [blame] | 511 | bool HDeadCodeElimination::Run() { |
Nicolas Geoffray | dac9b19 | 2016-07-15 10:46:17 +0100 | [diff] [blame] | 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; |
Aart Bik | a8b8e9b | 2018-01-09 11:01:02 -0800 | [diff] [blame] | 519 | did_any_simplification |= SimplifyAlwaysThrows(); |
Nicolas Geoffray | dac9b19 | 2016-07-15 10:46:17 +0100 | [diff] [blame] | 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 | } |
David Brazdil | 84daae5 | 2015-05-18 12:06:52 +0100 | [diff] [blame] | 527 | SsaRedundantPhiElimination(graph_).Run(); |
David Brazdil | 2d7352b | 2015-04-20 14:52:42 +0100 | [diff] [blame] | 528 | RemoveDeadInstructions(); |
Aart Bik | 2477320 | 2018-04-26 10:28:51 -0700 | [diff] [blame] | 529 | return true; |
David Brazdil | 2d7352b | 2015-04-20 14:52:42 +0100 | [diff] [blame] | 530 | } |
| 531 | |
Roland Levillain | 72bceff | 2014-09-15 18:29:00 +0100 | [diff] [blame] | 532 | } // namespace art |