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
3// BSD-style license that can be found in the LICENSE file.
4
5#include "vm/compiler/backend/branch_optimizer.h"
6
7#include "vm/compiler/backend/flow_graph.h"
8#include "vm/compiler/backend/il.h"
9
10namespace dart {
11
12// Returns true if the given phi has a single input use and
13// is used in the environments either at the corresponding block entry or
14// at the same instruction where input use is.
15static bool PhiHasSingleUse(PhiInstr* phi, Value* use) {
16 if ((use->next_use() != NULL) || (phi->input_use_list() != use)) {
17 return false;
18 }
19
20 BlockEntryInstr* block = phi->block();
21 for (Value* env_use = phi->env_use_list(); env_use != NULL;
22 env_use = env_use->next_use()) {
23 if ((env_use->instruction() != block) &&
24 (env_use->instruction() != use->instruction())) {
25 return false;
26 }
27 }
28
29 return true;
30}
31
32bool BranchSimplifier::Match(JoinEntryInstr* block) {
33 // Match the pattern of a branch on a comparison whose left operand is a
34 // phi from the same block, and whose right operand is a constant.
35 //
36 // Branch(Comparison(kind, Phi, Constant))
37 //
38 // These are the branches produced by inlining in a test context. Also,
39 // the phi has no other uses so they can simply be eliminated. The block
40 // has no other phis and no instructions intervening between the phi and
41 // branch so the block can simply be eliminated.
42 BranchInstr* branch = block->last_instruction()->AsBranch();
43 ASSERT(branch != NULL);
44 ComparisonInstr* comparison = branch->comparison();
45 if (comparison->InputCount() != 2) {
46 return false;
47 }
48 if (comparison->CanDeoptimize() || comparison->MayThrow()) {
49 return false;
50 }
51 Value* left = comparison->left();
52 PhiInstr* phi = left->definition()->AsPhi();
53 Value* right = comparison->right();
54 ConstantInstr* constant =
55 (right == NULL) ? NULL : right->definition()->AsConstant();
56 return (phi != NULL) && (constant != NULL) && (phi->GetBlock() == block) &&
57 PhiHasSingleUse(phi, left) && (block->next() == branch) &&
58 (block->phis()->length() == 1);
59}
60
61JoinEntryInstr* BranchSimplifier::ToJoinEntry(Zone* zone,
62 BlockEntryInstr* target) {
63 // Convert a target block into a join block. Branches will be duplicated
64 // so the former true and false targets become joins of the control flows
65 // from all the duplicated branches.
66 JoinEntryInstr* join = new (zone)
67 JoinEntryInstr(target->block_id(), target->try_index(), DeoptId::kNone);
68 join->InheritDeoptTarget(zone, target);
69 join->LinkTo(target->next());
70 join->set_last_instruction(target->last_instruction());
71 target->UnuseAllInputs();
72 return join;
73}
74
75TargetEntryInstr* BranchSimplifier::ToTargetEntry(Zone* zone,
76 BlockEntryInstr* target) {
77 auto replacement = new (zone)
78 TargetEntryInstr(target->block_id(), target->try_index(), DeoptId::kNone);
79 replacement->InheritDeoptTarget(zone, target);
80 replacement->LinkTo(target->next());
81 replacement->set_last_instruction(target->last_instruction());
82 target->UnuseAllInputs();
83 return replacement;
84}
85
86BranchInstr* BranchSimplifier::CloneBranch(Zone* zone,
87 BranchInstr* branch,
88 Value* new_left,
89 Value* new_right) {
90 ComparisonInstr* comparison = branch->comparison();
91 ComparisonInstr* new_comparison =
92 comparison->CopyWithNewOperands(new_left, new_right);
93 BranchInstr* new_branch =
94 new (zone) BranchInstr(new_comparison, DeoptId::kNone);
95 return new_branch;
96}
97
98void BranchSimplifier::Simplify(FlowGraph* flow_graph) {
99 // Optimize some branches that test the value of a phi. When it is safe
100 // to do so, push the branch to each of the predecessor blocks. This is
101 // an optimization when (a) it can avoid materializing a boolean object at
102 // the phi only to test its value, and (b) it can expose opportunities for
103 // constant propagation and unreachable code elimination. This
104 // optimization is intended to run after inlining which creates
105 // opportunities for optimization (a) and before constant folding which
106 // can perform optimization (b).
107
108 // Begin with a worklist of join blocks ending in branches. They are
109 // candidates for the pattern below.
110 Zone* zone = flow_graph->zone();
111 const GrowableArray<BlockEntryInstr*>& postorder = flow_graph->postorder();
112 GrowableArray<BlockEntryInstr*> worklist(postorder.length());
113 for (BlockIterator it(postorder); !it.Done(); it.Advance()) {
114 BlockEntryInstr* block = it.Current();
115 if (block->IsJoinEntry() && block->last_instruction()->IsBranch()) {
116 worklist.Add(block);
117 }
118 }
119
120 // Rewrite until no more instance of the pattern exists.
121 bool changed = false;
122 while (!worklist.is_empty()) {
123 // All blocks in the worklist are join blocks (ending with a branch).
124 JoinEntryInstr* block = worklist.RemoveLast()->AsJoinEntry();
125 ASSERT(block != NULL);
126
127 if (Match(block)) {
128 changed = true;
129
130 // The branch will be copied and pushed to all the join's
131 // predecessors. Convert the true and false target blocks into join
132 // blocks to join the control flows from all of the true
133 // (respectively, false) targets of the copied branches.
134 //
135 // The converted join block will have no phis, so it cannot be another
136 // instance of the pattern. There is thus no need to add it to the
137 // worklist.
138 BranchInstr* branch = block->last_instruction()->AsBranch();
139 ASSERT(branch != NULL);
140 JoinEntryInstr* join_true = ToJoinEntry(zone, branch->true_successor());
141 JoinEntryInstr* join_false = ToJoinEntry(zone, branch->false_successor());
142
143 ComparisonInstr* comparison = branch->comparison();
144 PhiInstr* phi = comparison->left()->definition()->AsPhi();
145 ConstantInstr* constant = comparison->right()->definition()->AsConstant();
146 ASSERT(constant != NULL);
147 // Copy the constant and branch and push it to all the predecessors.
148 for (intptr_t i = 0, count = block->PredecessorCount(); i < count; ++i) {
149 GotoInstr* old_goto =
150 block->PredecessorAt(i)->last_instruction()->AsGoto();
151 ASSERT(old_goto != NULL);
152
153 // Replace the goto in each predecessor with a rewritten branch,
154 // rewritten to use the corresponding phi input instead of the phi.
155 Value* new_left = phi->InputAt(i)->Copy(zone);
156 Value* new_right = new (zone) Value(constant);
157 BranchInstr* new_branch =
158 CloneBranch(zone, branch, new_left, new_right);
159 if (branch->env() == NULL) {
160 new_branch->InheritDeoptTarget(zone, old_goto);
161 } else {
162 // Take the environment from the branch if it has one.
163 new_branch->InheritDeoptTarget(zone, branch);
164 // InheritDeoptTarget gave the new branch's comparison the same
165 // deopt id that it gave the new branch. The id should be the
166 // deopt id of the original comparison.
167 new_branch->comparison()->SetDeoptId(*comparison);
168 // The phi can be used in the branch's environment. Rename such
169 // uses.
170 Definition* replacement = phi->InputAt(i)->definition();
171 new_branch->ReplaceInEnvironment(phi, replacement);
172 }
173
174 new_branch->InsertBefore(old_goto);
175 new_branch->set_next(NULL); // Detaching the goto from the graph.
176 old_goto->UnuseAllInputs();
177
178 // Update the predecessor block. We may have created another
179 // instance of the pattern so add it to the worklist if necessary.
180 BlockEntryInstr* branch_block = new_branch->GetBlock();
181 branch_block->set_last_instruction(new_branch);
182 if (branch_block->IsJoinEntry()) worklist.Add(branch_block);
183
184 // Connect the branch to the true and false joins, via empty target
185 // blocks.
186 TargetEntryInstr* true_target = new (zone) TargetEntryInstr(
187 flow_graph->max_block_id() + 1, block->try_index(), DeoptId::kNone);
188 true_target->InheritDeoptTarget(zone, join_true);
189 TargetEntryInstr* false_target = new (zone) TargetEntryInstr(
190 flow_graph->max_block_id() + 2, block->try_index(), DeoptId::kNone);
191 false_target->InheritDeoptTarget(zone, join_false);
192 flow_graph->set_max_block_id(flow_graph->max_block_id() + 2);
193 *new_branch->true_successor_address() = true_target;
194 *new_branch->false_successor_address() = false_target;
195 GotoInstr* goto_true = new (zone) GotoInstr(join_true, DeoptId::kNone);
196 goto_true->InheritDeoptTarget(zone, join_true);
197 true_target->LinkTo(goto_true);
198 true_target->set_last_instruction(goto_true);
199 GotoInstr* goto_false =
200 new (zone) GotoInstr(join_false, DeoptId::kNone);
201 goto_false->InheritDeoptTarget(zone, join_false);
202 false_target->LinkTo(goto_false);
203 false_target->set_last_instruction(goto_false);
204 }
205 // When all predecessors have been rewritten, the original block is
206 // unreachable from the graph.
207 phi->UnuseAllInputs();
208 branch->UnuseAllInputs();
209 block->UnuseAllInputs();
210 ASSERT(!phi->HasUses());
211 }
212 }
213
214 if (changed) {
215 // We may have changed the block order and the dominator tree.
216 flow_graph->DiscoverBlocks();
217 GrowableArray<BitVector*> dominance_frontier;
218 flow_graph->ComputeDominators(&dominance_frontier);
219 }
220}
221
222static bool IsTrivialBlock(BlockEntryInstr* block, Definition* defn) {
223 return (block->IsTargetEntry() && (block->PredecessorCount() == 1)) &&
224 ((block->next() == block->last_instruction()) ||
225 ((block->next() == defn) &&
226 (defn->next() == block->last_instruction())));
227}
228
229static void EliminateTrivialBlock(BlockEntryInstr* block,
230 Definition* instr,
231 IfThenElseInstr* before) {
232 block->UnuseAllInputs();
233 block->last_instruction()->UnuseAllInputs();
234
235 if ((block->next() == instr) &&
236 (instr->next() == block->last_instruction())) {
237 before->previous()->LinkTo(instr);
238 instr->LinkTo(before);
239 }
240}
241
242void IfConverter::Simplify(FlowGraph* flow_graph) {
243 Zone* zone = flow_graph->zone();
244 bool changed = false;
245
246 const GrowableArray<BlockEntryInstr*>& postorder = flow_graph->postorder();
247 for (BlockIterator it(postorder); !it.Done(); it.Advance()) {
248 BlockEntryInstr* block = it.Current();
249 JoinEntryInstr* join = block->AsJoinEntry();
250
251 // Detect diamond control flow pattern which materializes a value depending
252 // on the result of the comparison:
253 //
254 // B_pred:
255 // ...
256 // Branch if COMP goto (B_pred1, B_pred2)
257 // B_pred1: -- trivial block that contains at most one definition
258 // v1 = Constant(...)
259 // goto B_block
260 // B_pred2: -- trivial block that contains at most one definition
261 // v2 = Constant(...)
262 // goto B_block
263 // B_block:
264 // v3 = phi(v1, v2) -- single phi
265 //
266 // and replace it with
267 //
268 // Ba:
269 // v3 = IfThenElse(COMP ? v1 : v2)
270 //
271 if ((join != NULL) && (join->phis() != NULL) &&
272 (join->phis()->length() == 1) && (block->PredecessorCount() == 2)) {
273 BlockEntryInstr* pred1 = block->PredecessorAt(0);
274 BlockEntryInstr* pred2 = block->PredecessorAt(1);
275
276 PhiInstr* phi = (*join->phis())[0];
277 Value* v1 = phi->InputAt(0);
278 Value* v2 = phi->InputAt(1);
279
280 if (IsTrivialBlock(pred1, v1->definition()) &&
281 IsTrivialBlock(pred2, v2->definition()) &&
282 (pred1->PredecessorAt(0) == pred2->PredecessorAt(0))) {
283 BlockEntryInstr* pred = pred1->PredecessorAt(0);
284 BranchInstr* branch = pred->last_instruction()->AsBranch();
285
286 if (branch == nullptr) {
287 // There is no "B_pred" block.
288 ASSERT(pred->last_instruction()->IsGraphEntry());
289 continue;
290 }
291
292 ComparisonInstr* comparison = branch->comparison();
293
294 // Check if the platform supports efficient branchless IfThenElseInstr
295 // for the given combination of comparison and values flowing from
296 // false and true paths.
297 if (IfThenElseInstr::Supports(comparison, v1, v2)) {
298 Value* if_true = (pred1 == branch->true_successor()) ? v1 : v2;
299 Value* if_false = (pred2 == branch->true_successor()) ? v1 : v2;
300
301 ComparisonInstr* new_comparison = comparison->CopyWithNewOperands(
302 comparison->left()->Copy(zone), comparison->right()->Copy(zone));
303 IfThenElseInstr* if_then_else =
304 new (zone) IfThenElseInstr(new_comparison, if_true->Copy(zone),
305 if_false->Copy(zone), DeoptId::kNone);
306 flow_graph->InsertBefore(branch, if_then_else, NULL,
307 FlowGraph::kValue);
308
309 phi->ReplaceUsesWith(if_then_else);
310
311 // Connect IfThenElseInstr to the first instruction in the merge block
312 // effectively eliminating diamond control flow.
313 // Current block as well as pred1 and pred2 blocks are no longer in
314 // the graph at this point.
315 if_then_else->LinkTo(join->next());
316 pred->set_last_instruction(join->last_instruction());
317
318 // Resulting block must inherit block id from the eliminated current
319 // block to guarantee that ordering of phi operands in its successor
320 // stays consistent.
321 pred->set_block_id(block->block_id());
322
323 // If v1 and v2 were defined inside eliminated blocks pred1/pred2
324 // move them out to the place before inserted IfThenElse instruction.
325 EliminateTrivialBlock(pred1, v1->definition(), if_then_else);
326 EliminateTrivialBlock(pred2, v2->definition(), if_then_else);
327
328 // Update use lists to reflect changes in the graph.
329 phi->UnuseAllInputs();
330 branch->UnuseAllInputs();
331 block->UnuseAllInputs();
332
333 // The graph has changed. Recompute dominators and block orders after
334 // this pass is finished.
335 changed = true;
336 }
337 }
338 }
339 }
340
341 if (changed) {
342 // We may have changed the block order and the dominator tree.
343 flow_graph->DiscoverBlocks();
344 GrowableArray<BitVector*> dominance_frontier;
345 flow_graph->ComputeDominators(&dominance_frontier);
346 }
347}
348
349} // namespace dart
350