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 11 matching lines...) Expand all Loading... |
22 env_use = env_use->next_use()) { | 22 env_use = env_use->next_use()) { |
23 if ((env_use->instruction() != block) && | 23 if ((env_use->instruction() != block) && |
24 (env_use->instruction() != use->instruction())) { | 24 (env_use->instruction() != use->instruction())) { |
25 return false; | 25 return false; |
26 } | 26 } |
27 } | 27 } |
28 | 28 |
29 return true; | 29 return true; |
30 } | 30 } |
31 | 31 |
32 | |
33 bool BranchSimplifier::Match(JoinEntryInstr* block) { | 32 bool BranchSimplifier::Match(JoinEntryInstr* block) { |
34 // Match the pattern of a branch on a comparison whose left operand is a | 33 // Match the pattern of a branch on a comparison whose left operand is a |
35 // phi from the same block, and whose right operand is a constant. | 34 // phi from the same block, and whose right operand is a constant. |
36 // | 35 // |
37 // Branch(Comparison(kind, Phi, Constant)) | 36 // Branch(Comparison(kind, Phi, Constant)) |
38 // | 37 // |
39 // These are the branches produced by inlining in a test context. Also, | 38 // These are the branches produced by inlining in a test context. Also, |
40 // the phi has no other uses so they can simply be eliminated. The block | 39 // the phi has no other uses so they can simply be eliminated. The block |
41 // has no other phis and no instructions intervening between the phi and | 40 // has no other phis and no instructions intervening between the phi and |
42 // branch so the block can simply be eliminated. | 41 // branch so the block can simply be eliminated. |
43 BranchInstr* branch = block->last_instruction()->AsBranch(); | 42 BranchInstr* branch = block->last_instruction()->AsBranch(); |
44 ASSERT(branch != NULL); | 43 ASSERT(branch != NULL); |
45 ComparisonInstr* comparison = branch->comparison(); | 44 ComparisonInstr* comparison = branch->comparison(); |
46 if (comparison->InputCount() != 2) { | 45 if (comparison->InputCount() != 2) { |
47 return false; | 46 return false; |
48 } | 47 } |
49 if (comparison->CanDeoptimize() || comparison->MayThrow()) { | 48 if (comparison->CanDeoptimize() || comparison->MayThrow()) { |
50 return false; | 49 return false; |
51 } | 50 } |
52 Value* left = comparison->left(); | 51 Value* left = comparison->left(); |
53 PhiInstr* phi = left->definition()->AsPhi(); | 52 PhiInstr* phi = left->definition()->AsPhi(); |
54 Value* right = comparison->right(); | 53 Value* right = comparison->right(); |
55 ConstantInstr* constant = | 54 ConstantInstr* constant = |
56 (right == NULL) ? NULL : right->definition()->AsConstant(); | 55 (right == NULL) ? NULL : right->definition()->AsConstant(); |
57 return (phi != NULL) && (constant != NULL) && (phi->GetBlock() == block) && | 56 return (phi != NULL) && (constant != NULL) && (phi->GetBlock() == block) && |
58 PhiHasSingleUse(phi, left) && (block->next() == branch) && | 57 PhiHasSingleUse(phi, left) && (block->next() == branch) && |
59 (block->phis()->length() == 1); | 58 (block->phis()->length() == 1); |
60 } | 59 } |
61 | 60 |
62 | |
63 JoinEntryInstr* BranchSimplifier::ToJoinEntry(Zone* zone, | 61 JoinEntryInstr* BranchSimplifier::ToJoinEntry(Zone* zone, |
64 TargetEntryInstr* target) { | 62 TargetEntryInstr* target) { |
65 // Convert a target block into a join block. Branches will be duplicated | 63 // 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 | 64 // so the former true and false targets become joins of the control flows |
67 // from all the duplicated branches. | 65 // from all the duplicated branches. |
68 JoinEntryInstr* join = new (zone) JoinEntryInstr( | 66 JoinEntryInstr* join = new (zone) JoinEntryInstr( |
69 target->block_id(), target->try_index(), Thread::kNoDeoptId); | 67 target->block_id(), target->try_index(), Thread::kNoDeoptId); |
70 join->InheritDeoptTarget(zone, target); | 68 join->InheritDeoptTarget(zone, target); |
71 join->LinkTo(target->next()); | 69 join->LinkTo(target->next()); |
72 join->set_last_instruction(target->last_instruction()); | 70 join->set_last_instruction(target->last_instruction()); |
73 target->UnuseAllInputs(); | 71 target->UnuseAllInputs(); |
74 return join; | 72 return join; |
75 } | 73 } |
76 | 74 |
77 | |
78 BranchInstr* BranchSimplifier::CloneBranch(Zone* zone, | 75 BranchInstr* BranchSimplifier::CloneBranch(Zone* zone, |
79 BranchInstr* branch, | 76 BranchInstr* branch, |
80 Value* new_left, | 77 Value* new_left, |
81 Value* new_right) { | 78 Value* new_right) { |
82 ComparisonInstr* comparison = branch->comparison(); | 79 ComparisonInstr* comparison = branch->comparison(); |
83 ComparisonInstr* new_comparison = | 80 ComparisonInstr* new_comparison = |
84 comparison->CopyWithNewOperands(new_left, new_right); | 81 comparison->CopyWithNewOperands(new_left, new_right); |
85 BranchInstr* new_branch = | 82 BranchInstr* new_branch = |
86 new (zone) BranchInstr(new_comparison, Thread::kNoDeoptId); | 83 new (zone) BranchInstr(new_comparison, Thread::kNoDeoptId); |
87 return new_branch; | 84 return new_branch; |
88 } | 85 } |
89 | 86 |
90 | |
91 void BranchSimplifier::Simplify(FlowGraph* flow_graph) { | 87 void BranchSimplifier::Simplify(FlowGraph* flow_graph) { |
92 // Optimize some branches that test the value of a phi. When it is safe | 88 // 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 | 89 // 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 | 90 // 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 | 91 // the phi only to test its value, and (b) it can expose opportunities for |
96 // constant propagation and unreachable code elimination. This | 92 // constant propagation and unreachable code elimination. This |
97 // optimization is intended to run after inlining which creates | 93 // optimization is intended to run after inlining which creates |
98 // opportunities for optimization (a) and before constant folding which | 94 // opportunities for optimization (a) and before constant folding which |
99 // can perform optimization (b). | 95 // can perform optimization (b). |
100 | 96 |
(...skipping 115 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
216 } | 212 } |
217 | 213 |
218 if (changed) { | 214 if (changed) { |
219 // We may have changed the block order and the dominator tree. | 215 // We may have changed the block order and the dominator tree. |
220 flow_graph->DiscoverBlocks(); | 216 flow_graph->DiscoverBlocks(); |
221 GrowableArray<BitVector*> dominance_frontier; | 217 GrowableArray<BitVector*> dominance_frontier; |
222 flow_graph->ComputeDominators(&dominance_frontier); | 218 flow_graph->ComputeDominators(&dominance_frontier); |
223 } | 219 } |
224 } | 220 } |
225 | 221 |
226 | |
227 static bool IsTrivialBlock(BlockEntryInstr* block, Definition* defn) { | 222 static bool IsTrivialBlock(BlockEntryInstr* block, Definition* defn) { |
228 return (block->IsTargetEntry() && (block->PredecessorCount() == 1)) && | 223 return (block->IsTargetEntry() && (block->PredecessorCount() == 1)) && |
229 ((block->next() == block->last_instruction()) || | 224 ((block->next() == block->last_instruction()) || |
230 ((block->next() == defn) && | 225 ((block->next() == defn) && |
231 (defn->next() == block->last_instruction()))); | 226 (defn->next() == block->last_instruction()))); |
232 } | 227 } |
233 | 228 |
234 | |
235 static void EliminateTrivialBlock(BlockEntryInstr* block, | 229 static void EliminateTrivialBlock(BlockEntryInstr* block, |
236 Definition* instr, | 230 Definition* instr, |
237 IfThenElseInstr* before) { | 231 IfThenElseInstr* before) { |
238 block->UnuseAllInputs(); | 232 block->UnuseAllInputs(); |
239 block->last_instruction()->UnuseAllInputs(); | 233 block->last_instruction()->UnuseAllInputs(); |
240 | 234 |
241 if ((block->next() == instr) && | 235 if ((block->next() == instr) && |
242 (instr->next() == block->last_instruction())) { | 236 (instr->next() == block->last_instruction())) { |
243 before->previous()->LinkTo(instr); | 237 before->previous()->LinkTo(instr); |
244 instr->LinkTo(before); | 238 instr->LinkTo(before); |
245 } | 239 } |
246 } | 240 } |
247 | 241 |
248 | |
249 void IfConverter::Simplify(FlowGraph* flow_graph) { | 242 void IfConverter::Simplify(FlowGraph* flow_graph) { |
250 Zone* zone = flow_graph->zone(); | 243 Zone* zone = flow_graph->zone(); |
251 bool changed = false; | 244 bool changed = false; |
252 | 245 |
253 const GrowableArray<BlockEntryInstr*>& postorder = flow_graph->postorder(); | 246 const GrowableArray<BlockEntryInstr*>& postorder = flow_graph->postorder(); |
254 for (BlockIterator it(postorder); !it.Done(); it.Advance()) { | 247 for (BlockIterator it(postorder); !it.Done(); it.Advance()) { |
255 BlockEntryInstr* block = it.Current(); | 248 BlockEntryInstr* block = it.Current(); |
256 JoinEntryInstr* join = block->AsJoinEntry(); | 249 JoinEntryInstr* join = block->AsJoinEntry(); |
257 | 250 |
258 // Detect diamond control flow pattern which materializes a value depending | 251 // Detect diamond control flow pattern which materializes a value depending |
(...skipping 80 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
339 } | 332 } |
340 | 333 |
341 if (changed) { | 334 if (changed) { |
342 // We may have changed the block order and the dominator tree. | 335 // We may have changed the block order and the dominator tree. |
343 flow_graph->DiscoverBlocks(); | 336 flow_graph->DiscoverBlocks(); |
344 GrowableArray<BitVector*> dominance_frontier; | 337 GrowableArray<BitVector*> dominance_frontier; |
345 flow_graph->ComputeDominators(&dominance_frontier); | 338 flow_graph->ComputeDominators(&dominance_frontier); |
346 } | 339 } |
347 } | 340 } |
348 | 341 |
349 | |
350 } // namespace dart | 342 } // namespace dart |
OLD | NEW |