blob: 3c586358a76d605492a860efceabcecffc9f170b [file] [log] [blame]
// 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() != NULL) || (phi->input_use_list() != use)) {
return false;
BlockEntryInstr* block = phi->block();
for (Value* env_use = phi->env_use_list(); env_use != NULL;
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 comparison whose left operand is a
// phi from the same block, and whose right operand is a constant.
// Branch(Comparison(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 != NULL);
ComparisonInstr* comparison = branch->comparison();
if (comparison->InputCount() != 2) {
return false;
if (comparison->CanDeoptimize() || comparison->MayThrow()) {
return false;
Value* left = comparison->left();
PhiInstr* phi = left->definition()->AsPhi();
Value* right = comparison->right();
ConstantInstr* constant =
(right == NULL) ? NULL : right->definition()->AsConstant();
return (phi != NULL) && (constant != NULL) && (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);
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);
return replacement;
BranchInstr* BranchSimplifier::CloneBranch(Zone* zone,
BranchInstr* branch,
Value* new_left,
Value* new_right) {
ComparisonInstr* comparison = branch->comparison();
ComparisonInstr* new_comparison =
comparison->CopyWithNewOperands(new_left, new_right);
BranchInstr* new_branch =
new (zone) BranchInstr(new_comparison, 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()) {
// 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 != NULL);
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 != NULL);
JoinEntryInstr* join_true = ToJoinEntry(zone, branch->true_successor());
JoinEntryInstr* join_false = ToJoinEntry(zone, branch->false_successor());
ComparisonInstr* comparison = branch->comparison();
PhiInstr* phi = comparison->left()->definition()->AsPhi();
ConstantInstr* constant = comparison->right()->definition()->AsConstant();
ASSERT(constant != NULL);
// 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 =
ASSERT(old_goto != NULL);
// 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() == NULL) {
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 comparison the same
// deopt id that it gave the new branch. The id should be the
// deopt id of the original comparison.
// 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->set_next(NULL); // Detaching the goto from the graph.
// 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();
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);
GotoInstr* goto_false =
new (zone) GotoInstr(join_false, DeoptId::kNone);
goto_false->InheritDeoptTarget(zone, join_false);
// When all predecessors have been rewritten, the original block is
// unreachable from the graph.
if (changed) {
// We may have changed the block order and the dominator tree.
GrowableArray<BitVector*> 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) {
if ((block->next() == instr) &&
(instr->next() == block->last_instruction())) {
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 comparison:
// B_pred:
// ...
// Branch if COMP 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(COMP ? v1 : v2)
if ((join != NULL) && (join->phis() != NULL) &&
(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.
ComparisonInstr* comparison = branch->comparison();
// Check if the platform supports efficient branchless IfThenElseInstr
// for the given combination of comparison and values flowing from
// false and true paths.
if (IfThenElseInstr::Supports(comparison, v1, v2)) {
Value* if_true = (pred1 == branch->true_successor()) ? v1 : v2;
Value* if_false = (pred2 == branch->true_successor()) ? v1 : v2;
ComparisonInstr* new_comparison = comparison->CopyWithNewOperands(
comparison->left()->Copy(zone), comparison->right()->Copy(zone));
IfThenElseInstr* if_then_else =
new (zone) IfThenElseInstr(new_comparison, if_true->Copy(zone),
if_false->Copy(zone), DeoptId::kNone);
flow_graph->InsertBefore(branch, if_then_else, NULL,
// 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.
// Resulting block must inherit block id from the eliminated current
// block to guarantee that ordering of phi operands in its successor
// stays consistent.
// 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.
// 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.
GrowableArray<BitVector*> dominance_frontier;
} // namespace dart