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 |