| // Copyright (c) 2016, the Dart project authors. Please see the AUTHORS file | |
| // for details. All rights reserved. Use of this source code is governed by a | |
| // BSD-style license that can be found in the LICENSE file. | |
| #include "vm/compiler/backend/branch_optimizer.h" | |
| #include "vm/compiler/backend/flow_graph.h" | |
| #include "vm/compiler/backend/il.h" | |
| namespace dart { | |
| // Returns true if the given phi has a single input use and | |
| // is used in the environments either at the corresponding block entry or | |
| // at the same instruction where input use is. | |
| static bool PhiHasSingleUse(PhiInstr* phi, Value* use) { | |
| if ((use->next_use() != nullptr) || (phi->input_use_list() != use)) { | |
| return false; | |
| } | |
| BlockEntryInstr* block = phi->block(); | |
| for (Value* env_use = phi->env_use_list(); env_use != nullptr; | |
| env_use = env_use->next_use()) { | |
| if ((env_use->instruction() != block) && | |
| (env_use->instruction() != use->instruction())) { | |
| return false; | |
| } | |
| } | |
| return true; | |
| } | |
| bool BranchSimplifier::Match(JoinEntryInstr* block) { | |
| // Match the pattern of a branch on a condition whose left operand is a | |
| // phi from the same block, and whose right operand is a constant. | |
| // | |
| // Branch(Condition(kind, Phi, Constant)) | |
| // | |
| // These are the branches produced by inlining in a test context. Also, | |
| // the phi has no other uses so they can simply be eliminated. The block | |
| // has no other phis and no instructions intervening between the phi and | |
| // branch so the block can simply be eliminated. | |
| BranchInstr* branch = block->last_instruction()->AsBranch(); | |
| ASSERT(branch != nullptr); | |
| ConditionInstr* condition = branch->condition(); | |
| if (condition->InputCount() != 2) { | |
| return false; | |
| } | |
| if (condition->CanDeoptimize() || condition->MayThrow()) { | |
| return false; | |
| } | |
| Value* left = condition->InputAt(0); | |
| PhiInstr* phi = left->definition()->AsPhi(); | |
| Value* right = condition->InputAt(1); | |
| ConstantInstr* constant = | |
| (right == nullptr) ? nullptr : right->definition()->AsConstant(); | |
| return (phi != nullptr) && (constant != nullptr) && | |
| (phi->GetBlock() == block) && PhiHasSingleUse(phi, left) && | |
| (block->next() == branch) && (block->phis()->length() == 1); | |
| } | |
| JoinEntryInstr* BranchSimplifier::ToJoinEntry(Zone* zone, | |
| BlockEntryInstr* target) { | |
| // Convert a target block into a join block. Branches will be duplicated | |
| // so the former true and false targets become joins of the control flows | |
| // from all the duplicated branches. | |
| JoinEntryInstr* join = new (zone) | |
| JoinEntryInstr(target->block_id(), target->try_index(), DeoptId::kNone); | |
| join->InheritDeoptTarget(zone, target); | |
| join->LinkTo(target->next()); | |
| join->set_last_instruction(target->last_instruction()); | |
| target->UnuseAllInputs(); | |
| return join; | |
| } | |
| TargetEntryInstr* BranchSimplifier::ToTargetEntry(Zone* zone, | |
| BlockEntryInstr* target) { | |
| auto replacement = new (zone) | |
| TargetEntryInstr(target->block_id(), target->try_index(), DeoptId::kNone); | |
| replacement->InheritDeoptTarget(zone, target); | |
| replacement->LinkTo(target->next()); | |
| replacement->set_last_instruction(target->last_instruction()); | |
| target->UnuseAllInputs(); | |
| return replacement; | |
| } | |
| BranchInstr* BranchSimplifier::CloneBranch(Zone* zone, | |
| BranchInstr* branch, | |
| Value* new_left, | |
| Value* new_right) { | |
| ConditionInstr* condition = branch->condition(); | |
| ConditionInstr* new_condition = | |
| condition->CopyWithNewOperands(new_left, new_right); | |
| BranchInstr* new_branch = | |
| new (zone) BranchInstr(new_condition, DeoptId::kNone); | |
| return new_branch; | |
| } | |
| void BranchSimplifier::Simplify(FlowGraph* flow_graph) { | |
| // Optimize some branches that test the value of a phi. When it is safe | |
| // to do so, push the branch to each of the predecessor blocks. This is | |
| // an optimization when (a) it can avoid materializing a boolean object at | |
| // the phi only to test its value, and (b) it can expose opportunities for | |
| // constant propagation and unreachable code elimination. This | |
| // optimization is intended to run after inlining which creates | |
| // opportunities for optimization (a) and before constant folding which | |
| // can perform optimization (b). | |
| // Begin with a worklist of join blocks ending in branches. They are | |
| // candidates for the pattern below. | |
| Zone* zone = flow_graph->zone(); | |
| const GrowableArray<BlockEntryInstr*>& postorder = flow_graph->postorder(); | |
| GrowableArray<BlockEntryInstr*> worklist(postorder.length()); | |
| for (BlockIterator it(postorder); !it.Done(); it.Advance()) { | |
| BlockEntryInstr* block = it.Current(); | |
| if (block->IsJoinEntry() && block->last_instruction()->IsBranch()) { | |
| worklist.Add(block); | |
| } | |
| } | |
| // Rewrite until no more instance of the pattern exists. | |
| bool changed = false; | |
| while (!worklist.is_empty()) { | |
| // All blocks in the worklist are join blocks (ending with a branch). | |
| JoinEntryInstr* block = worklist.RemoveLast()->AsJoinEntry(); | |
| ASSERT(block != nullptr); | |
| if (Match(block)) { | |
| changed = true; | |
| // The branch will be copied and pushed to all the join's | |
| // predecessors. Convert the true and false target blocks into join | |
| // blocks to join the control flows from all of the true | |
| // (respectively, false) targets of the copied branches. | |
| // | |
| // The converted join block will have no phis, so it cannot be another | |
| // instance of the pattern. There is thus no need to add it to the | |
| // worklist. | |
| BranchInstr* branch = block->last_instruction()->AsBranch(); | |
| ASSERT(branch != nullptr); | |
| JoinEntryInstr* join_true = ToJoinEntry(zone, branch->true_successor()); | |
| JoinEntryInstr* join_false = ToJoinEntry(zone, branch->false_successor()); | |
| ConditionInstr* condition = branch->condition(); | |
| PhiInstr* phi = condition->InputAt(0)->definition()->AsPhi(); | |
| ConstantInstr* constant = | |
| condition->InputAt(1)->definition()->AsConstant(); | |
| ASSERT(constant != nullptr); | |
| // Copy the constant and branch and push it to all the predecessors. | |
| for (intptr_t i = 0, count = block->PredecessorCount(); i < count; ++i) { | |
| GotoInstr* old_goto = | |
| block->PredecessorAt(i)->last_instruction()->AsGoto(); | |
| ASSERT(old_goto != nullptr); | |
| // Replace the goto in each predecessor with a rewritten branch, | |
| // rewritten to use the corresponding phi input instead of the phi. | |
| Value* new_left = phi->InputAt(i)->Copy(zone); | |
| Value* new_right = new (zone) Value(constant); | |
| BranchInstr* new_branch = | |
| CloneBranch(zone, branch, new_left, new_right); | |
| if (branch->env() == nullptr) { | |
| new_branch->InheritDeoptTarget(zone, old_goto); | |
| } else { | |
| // Take the environment from the branch if it has one. | |
| new_branch->InheritDeoptTarget(zone, branch); | |
| // InheritDeoptTarget gave the new branch's condition the same | |
| // deopt id that it gave the new branch. The id should be the | |
| // deopt id of the original condition. | |
| new_branch->condition()->SetDeoptId(*condition); | |
| // The phi can be used in the branch's environment. Rename such | |
| // uses. | |
| Definition* replacement = phi->InputAt(i)->definition(); | |
| new_branch->ReplaceInEnvironment(phi, replacement); | |
| } | |
| new_branch->InsertBefore(old_goto); | |
| new_branch->set_next(nullptr); // Detaching the goto from the graph. | |
| old_goto->UnuseAllInputs(); | |
| // Update the predecessor block. We may have created another | |
| // instance of the pattern so add it to the worklist if necessary. | |
| BlockEntryInstr* branch_block = new_branch->GetBlock(); | |
| branch_block->set_last_instruction(new_branch); | |
| if (branch_block->IsJoinEntry()) worklist.Add(branch_block); | |
| // Connect the branch to the true and false joins, via empty target | |
| // blocks. | |
| TargetEntryInstr* true_target = new (zone) TargetEntryInstr( | |
| flow_graph->max_block_id() + 1, block->try_index(), DeoptId::kNone); | |
| true_target->InheritDeoptTarget(zone, join_true); | |
| TargetEntryInstr* false_target = new (zone) TargetEntryInstr( | |
| flow_graph->max_block_id() + 2, block->try_index(), DeoptId::kNone); | |
| false_target->InheritDeoptTarget(zone, join_false); | |
| flow_graph->set_max_block_id(flow_graph->max_block_id() + 2); | |
| *new_branch->true_successor_address() = true_target; | |
| *new_branch->false_successor_address() = false_target; | |
| GotoInstr* goto_true = new (zone) GotoInstr(join_true, DeoptId::kNone); | |
| goto_true->InheritDeoptTarget(zone, join_true); | |
| true_target->LinkTo(goto_true); | |
| true_target->set_last_instruction(goto_true); | |
| GotoInstr* goto_false = | |
| new (zone) GotoInstr(join_false, DeoptId::kNone); | |
| goto_false->InheritDeoptTarget(zone, join_false); | |
| false_target->LinkTo(goto_false); | |
| false_target->set_last_instruction(goto_false); | |
| } | |
| // When all predecessors have been rewritten, the original block is | |
| // unreachable from the graph. | |
| phi->UnuseAllInputs(); | |
| branch->UnuseAllInputs(); | |
| block->UnuseAllInputs(); | |
| ASSERT(!phi->HasUses()); | |
| } | |
| } | |
| if (changed) { | |
| // We may have changed the block order and the dominator tree. | |
| flow_graph->DiscoverBlocks(); | |
| GrowableArray<BitVector*> dominance_frontier; | |
| flow_graph->ComputeDominators(&dominance_frontier); | |
| } | |
| } | |
| static bool IsTrivialBlock(BlockEntryInstr* block, Definition* defn) { | |
| return (block->IsTargetEntry() && (block->PredecessorCount() == 1)) && | |
| ((block->next() == block->last_instruction()) || | |
| ((block->next() == defn) && | |
| (defn->next() == block->last_instruction()))); | |
| } | |
| static void EliminateTrivialBlock(BlockEntryInstr* block, | |
| Definition* instr, | |
| IfThenElseInstr* before) { | |
| block->UnuseAllInputs(); | |
| block->last_instruction()->UnuseAllInputs(); | |
| if ((block->next() == instr) && | |
| (instr->next() == block->last_instruction())) { | |
| before->previous()->LinkTo(instr); | |
| instr->LinkTo(before); | |
| } | |
| } | |
| void IfConverter::Simplify(FlowGraph* flow_graph) { | |
| Zone* zone = flow_graph->zone(); | |
| bool changed = false; | |
| const GrowableArray<BlockEntryInstr*>& postorder = flow_graph->postorder(); | |
| for (BlockIterator it(postorder); !it.Done(); it.Advance()) { | |
| BlockEntryInstr* block = it.Current(); | |
| JoinEntryInstr* join = block->AsJoinEntry(); | |
| // Detect diamond control flow pattern which materializes a value depending | |
| // on the result of the condition: | |
| // | |
| // B_pred: | |
| // ... | |
| // Branch if COND goto (B_pred1, B_pred2) | |
| // B_pred1: -- trivial block that contains at most one definition | |
| // v1 = Constant(...) | |
| // goto B_block | |
| // B_pred2: -- trivial block that contains at most one definition | |
| // v2 = Constant(...) | |
| // goto B_block | |
| // B_block: | |
| // v3 = phi(v1, v2) -- single phi | |
| // | |
| // and replace it with | |
| // | |
| // Ba: | |
| // v3 = IfThenElse(COND ? v1 : v2) | |
| // | |
| if ((join != nullptr) && (join->phis() != nullptr) && | |
| (join->phis()->length() == 1) && (block->PredecessorCount() == 2)) { | |
| BlockEntryInstr* pred1 = block->PredecessorAt(0); | |
| BlockEntryInstr* pred2 = block->PredecessorAt(1); | |
| PhiInstr* phi = (*join->phis())[0]; | |
| Value* v1 = phi->InputAt(0); | |
| Value* v2 = phi->InputAt(1); | |
| if (IsTrivialBlock(pred1, v1->definition()) && | |
| IsTrivialBlock(pred2, v2->definition()) && | |
| (pred1->PredecessorAt(0) == pred2->PredecessorAt(0))) { | |
| BlockEntryInstr* pred = pred1->PredecessorAt(0); | |
| BranchInstr* branch = pred->last_instruction()->AsBranch(); | |
| if (branch == nullptr) { | |
| // There is no "B_pred" block, or the block is the IndirectGoto | |
| // of a switch that uses it as a jump table. | |
| ASSERT(pred->last_instruction()->IsGraphEntry() || | |
| pred->last_instruction()->IsIndirectGoto()); | |
| continue; | |
| } | |
| ConditionInstr* condition = branch->condition(); | |
| // Check if the platform supports efficient branchless IfThenElseInstr | |
| // for the given combination of condition and values flowing from | |
| // false and true paths. | |
| if (IfThenElseInstr::Supports(condition, v1, v2)) { | |
| Value* if_true = (pred1 == branch->true_successor()) ? v1 : v2; | |
| Value* if_false = (pred2 == branch->true_successor()) ? v1 : v2; | |
| ConditionInstr* new_condition = | |
| condition->CopyWithNewOperands(condition->InputAt(0)->Copy(zone), | |
| condition->InputAt(1)->Copy(zone)); | |
| IfThenElseInstr* if_then_else = | |
| new (zone) IfThenElseInstr(new_condition, if_true->Copy(zone), | |
| if_false->Copy(zone), DeoptId::kNone); | |
| flow_graph->InsertBefore(branch, if_then_else, nullptr, | |
| FlowGraph::kValue); | |
| phi->ReplaceUsesWith(if_then_else); | |
| // Connect IfThenElseInstr to the first instruction in the merge block | |
| // effectively eliminating diamond control flow. | |
| // Current block as well as pred1 and pred2 blocks are no longer in | |
| // the graph at this point. | |
| if_then_else->LinkTo(join->next()); | |
| pred->set_last_instruction(join->last_instruction()); | |
| // Resulting block must inherit block id from the eliminated current | |
| // block to guarantee that ordering of phi operands in its successor | |
| // stays consistent. | |
| pred->set_block_id(block->block_id()); | |
| // If v1 and v2 were defined inside eliminated blocks pred1/pred2 | |
| // move them out to the place before inserted IfThenElse instruction. | |
| EliminateTrivialBlock(pred1, v1->definition(), if_then_else); | |
| EliminateTrivialBlock(pred2, v2->definition(), if_then_else); | |
| // Update use lists to reflect changes in the graph. | |
| phi->UnuseAllInputs(); | |
| branch->UnuseAllInputs(); | |
| block->UnuseAllInputs(); | |
| // The graph has changed. Recompute dominators and block orders after | |
| // this pass is finished. | |
| changed = true; | |
| } | |
| } | |
| } | |
| } | |
| if (changed) { | |
| // We may have changed the block order and the dominator tree. | |
| flow_graph->DiscoverBlocks(); | |
| GrowableArray<BitVector*> dominance_frontier; | |
| flow_graph->ComputeDominators(&dominance_frontier); | |
| } | |
| } | |
| } // namespace dart |