| OLD | NEW |
| 1 // Copyright (c) 2016, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2016, the Dart project authors. Please see the AUTHORS file |
| 2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
| 3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
| 4 | 4 |
| 5 #include "vm/branch_optimizer.h" | 5 #include "vm/branch_optimizer.h" |
| 6 | 6 |
| 7 #include "vm/flow_graph.h" | 7 #include "vm/flow_graph.h" |
| 8 #include "vm/intermediate_language.h" | 8 #include "vm/intermediate_language.h" |
| 9 | 9 |
| 10 namespace dart { | 10 namespace dart { |
| (...skipping 47 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 58 PhiHasSingleUse(phi, left) && (block->next() == branch) && | 58 PhiHasSingleUse(phi, left) && (block->next() == branch) && |
| 59 (block->phis()->length() == 1); | 59 (block->phis()->length() == 1); |
| 60 } | 60 } |
| 61 | 61 |
| 62 | 62 |
| 63 JoinEntryInstr* BranchSimplifier::ToJoinEntry(Zone* zone, | 63 JoinEntryInstr* BranchSimplifier::ToJoinEntry(Zone* zone, |
| 64 TargetEntryInstr* target) { | 64 TargetEntryInstr* target) { |
| 65 // Convert a target block into a join block. Branches will be duplicated | 65 // Convert a target block into a join block. Branches will be duplicated |
| 66 // so the former true and false targets become joins of the control flows | 66 // so the former true and false targets become joins of the control flows |
| 67 // from all the duplicated branches. | 67 // from all the duplicated branches. |
| 68 JoinEntryInstr* join = new (zone) JoinEntryInstr( | 68 JoinEntryInstr* join = |
| 69 target->block_id(), target->try_index(), Thread::kNoDeoptId); | 69 new (zone) JoinEntryInstr(target->block_id(), target->try_index()); |
| 70 join->InheritDeoptTarget(zone, target); | 70 join->InheritDeoptTarget(zone, target); |
| 71 join->LinkTo(target->next()); | 71 join->LinkTo(target->next()); |
| 72 join->set_last_instruction(target->last_instruction()); | 72 join->set_last_instruction(target->last_instruction()); |
| 73 target->UnuseAllInputs(); | 73 target->UnuseAllInputs(); |
| 74 return join; | 74 return join; |
| 75 } | 75 } |
| 76 | 76 |
| 77 | 77 |
| 78 BranchInstr* BranchSimplifier::CloneBranch(Zone* zone, | 78 BranchInstr* BranchSimplifier::CloneBranch(Zone* zone, |
| 79 BranchInstr* branch, | 79 BranchInstr* branch, |
| 80 Value* new_left, | 80 Value* new_left, |
| 81 Value* new_right) { | 81 Value* new_right) { |
| 82 ComparisonInstr* comparison = branch->comparison(); | 82 ComparisonInstr* comparison = branch->comparison(); |
| 83 ComparisonInstr* new_comparison = | 83 ComparisonInstr* new_comparison = |
| 84 comparison->CopyWithNewOperands(new_left, new_right); | 84 comparison->CopyWithNewOperands(new_left, new_right); |
| 85 BranchInstr* new_branch = | 85 BranchInstr* new_branch = new (zone) BranchInstr(new_comparison); |
| 86 new (zone) BranchInstr(new_comparison, Thread::kNoDeoptId); | |
| 87 return new_branch; | 86 return new_branch; |
| 88 } | 87 } |
| 89 | 88 |
| 90 | 89 |
| 91 void BranchSimplifier::Simplify(FlowGraph* flow_graph) { | 90 void BranchSimplifier::Simplify(FlowGraph* flow_graph) { |
| 92 // Optimize some branches that test the value of a phi. When it is safe | 91 // Optimize some branches that test the value of a phi. When it is safe |
| 93 // to do so, push the branch to each of the predecessor blocks. This is | 92 // to do so, push the branch to each of the predecessor blocks. This is |
| 94 // an optimization when (a) it can avoid materializing a boolean object at | 93 // an optimization when (a) it can avoid materializing a boolean object at |
| 95 // the phi only to test its value, and (b) it can expose opportunities for | 94 // the phi only to test its value, and (b) it can expose opportunities for |
| 96 // constant propagation and unreachable code elimination. This | 95 // constant propagation and unreachable code elimination. This |
| (...skipping 80 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 177 old_goto->UnuseAllInputs(); | 176 old_goto->UnuseAllInputs(); |
| 178 | 177 |
| 179 // Update the predecessor block. We may have created another | 178 // Update the predecessor block. We may have created another |
| 180 // instance of the pattern so add it to the worklist if necessary. | 179 // instance of the pattern so add it to the worklist if necessary. |
| 181 BlockEntryInstr* branch_block = new_branch->GetBlock(); | 180 BlockEntryInstr* branch_block = new_branch->GetBlock(); |
| 182 branch_block->set_last_instruction(new_branch); | 181 branch_block->set_last_instruction(new_branch); |
| 183 if (branch_block->IsJoinEntry()) worklist.Add(branch_block); | 182 if (branch_block->IsJoinEntry()) worklist.Add(branch_block); |
| 184 | 183 |
| 185 // Connect the branch to the true and false joins, via empty target | 184 // Connect the branch to the true and false joins, via empty target |
| 186 // blocks. | 185 // blocks. |
| 187 TargetEntryInstr* true_target = | 186 TargetEntryInstr* true_target = new (zone) TargetEntryInstr( |
| 188 new (zone) TargetEntryInstr(flow_graph->max_block_id() + 1, | 187 flow_graph->max_block_id() + 1, block->try_index()); |
| 189 block->try_index(), Thread::kNoDeoptId); | |
| 190 true_target->InheritDeoptTarget(zone, join_true); | 188 true_target->InheritDeoptTarget(zone, join_true); |
| 191 TargetEntryInstr* false_target = | 189 TargetEntryInstr* false_target = new (zone) TargetEntryInstr( |
| 192 new (zone) TargetEntryInstr(flow_graph->max_block_id() + 2, | 190 flow_graph->max_block_id() + 2, block->try_index()); |
| 193 block->try_index(), Thread::kNoDeoptId); | |
| 194 false_target->InheritDeoptTarget(zone, join_false); | 191 false_target->InheritDeoptTarget(zone, join_false); |
| 195 flow_graph->set_max_block_id(flow_graph->max_block_id() + 2); | 192 flow_graph->set_max_block_id(flow_graph->max_block_id() + 2); |
| 196 *new_branch->true_successor_address() = true_target; | 193 *new_branch->true_successor_address() = true_target; |
| 197 *new_branch->false_successor_address() = false_target; | 194 *new_branch->false_successor_address() = false_target; |
| 198 GotoInstr* goto_true = | 195 GotoInstr* goto_true = new (zone) GotoInstr(join_true); |
| 199 new (zone) GotoInstr(join_true, Thread::kNoDeoptId); | |
| 200 goto_true->InheritDeoptTarget(zone, join_true); | 196 goto_true->InheritDeoptTarget(zone, join_true); |
| 201 true_target->LinkTo(goto_true); | 197 true_target->LinkTo(goto_true); |
| 202 true_target->set_last_instruction(goto_true); | 198 true_target->set_last_instruction(goto_true); |
| 203 GotoInstr* goto_false = | 199 GotoInstr* goto_false = new (zone) GotoInstr(join_false); |
| 204 new (zone) GotoInstr(join_false, Thread::kNoDeoptId); | |
| 205 goto_false->InheritDeoptTarget(zone, join_false); | 200 goto_false->InheritDeoptTarget(zone, join_false); |
| 206 false_target->LinkTo(goto_false); | 201 false_target->LinkTo(goto_false); |
| 207 false_target->set_last_instruction(goto_false); | 202 false_target->set_last_instruction(goto_false); |
| 208 } | 203 } |
| 209 // When all predecessors have been rewritten, the original block is | 204 // When all predecessors have been rewritten, the original block is |
| 210 // unreachable from the graph. | 205 // unreachable from the graph. |
| 211 phi->UnuseAllInputs(); | 206 phi->UnuseAllInputs(); |
| 212 branch->UnuseAllInputs(); | 207 branch->UnuseAllInputs(); |
| 213 block->UnuseAllInputs(); | 208 block->UnuseAllInputs(); |
| 214 ASSERT(!phi->HasUses()); | 209 ASSERT(!phi->HasUses()); |
| (...skipping 78 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 293 | 288 |
| 294 // Check if the platform supports efficient branchless IfThenElseInstr | 289 // Check if the platform supports efficient branchless IfThenElseInstr |
| 295 // for the given combination of comparison and values flowing from | 290 // for the given combination of comparison and values flowing from |
| 296 // false and true paths. | 291 // false and true paths. |
| 297 if (IfThenElseInstr::Supports(comparison, v1, v2)) { | 292 if (IfThenElseInstr::Supports(comparison, v1, v2)) { |
| 298 Value* if_true = (pred1 == branch->true_successor()) ? v1 : v2; | 293 Value* if_true = (pred1 == branch->true_successor()) ? v1 : v2; |
| 299 Value* if_false = (pred2 == branch->true_successor()) ? v1 : v2; | 294 Value* if_false = (pred2 == branch->true_successor()) ? v1 : v2; |
| 300 | 295 |
| 301 ComparisonInstr* new_comparison = comparison->CopyWithNewOperands( | 296 ComparisonInstr* new_comparison = comparison->CopyWithNewOperands( |
| 302 comparison->left()->Copy(zone), comparison->right()->Copy(zone)); | 297 comparison->left()->Copy(zone), comparison->right()->Copy(zone)); |
| 303 IfThenElseInstr* if_then_else = new (zone) | 298 IfThenElseInstr* if_then_else = new (zone) IfThenElseInstr( |
| 304 IfThenElseInstr(new_comparison, if_true->Copy(zone), | 299 new_comparison, if_true->Copy(zone), if_false->Copy(zone)); |
| 305 if_false->Copy(zone), Thread::kNoDeoptId); | |
| 306 flow_graph->InsertBefore(branch, if_then_else, NULL, | 300 flow_graph->InsertBefore(branch, if_then_else, NULL, |
| 307 FlowGraph::kValue); | 301 FlowGraph::kValue); |
| 308 | 302 |
| 309 phi->ReplaceUsesWith(if_then_else); | 303 phi->ReplaceUsesWith(if_then_else); |
| 310 | 304 |
| 311 // Connect IfThenElseInstr to the first instruction in the merge block | 305 // Connect IfThenElseInstr to the first instruction in the merge block |
| 312 // effectively eliminating diamond control flow. | 306 // effectively eliminating diamond control flow. |
| 313 // Current block as well as pred1 and pred2 blocks are no longer in | 307 // Current block as well as pred1 and pred2 blocks are no longer in |
| 314 // the graph at this point. | 308 // the graph at this point. |
| 315 if_then_else->LinkTo(join->next()); | 309 if_then_else->LinkTo(join->next()); |
| (...skipping 25 matching lines...) Expand all Loading... |
| 341 if (changed) { | 335 if (changed) { |
| 342 // We may have changed the block order and the dominator tree. | 336 // We may have changed the block order and the dominator tree. |
| 343 flow_graph->DiscoverBlocks(); | 337 flow_graph->DiscoverBlocks(); |
| 344 GrowableArray<BitVector*> dominance_frontier; | 338 GrowableArray<BitVector*> dominance_frontier; |
| 345 flow_graph->ComputeDominators(&dominance_frontier); | 339 flow_graph->ComputeDominators(&dominance_frontier); |
| 346 } | 340 } |
| 347 } | 341 } |
| 348 | 342 |
| 349 | 343 |
| 350 } // namespace dart | 344 } // namespace dart |
| OLD | NEW |