dart::BranchSimplifier Class Reference

#include <branch_optimizer.h>

Inheritance diagram for dart::BranchSimplifier:

Static Public Member Functions
static void	Simplify (FlowGraph *flow_graph)
static JoinEntryInstr *	ToJoinEntry (Zone *zone, BlockEntryInstr *target)
static TargetEntryInstr *	ToTargetEntry (Zone *zone, BlockEntryInstr *target)

Detailed Description

Definition at line 28 of file branch_optimizer.h.

Member Function Documentation

Simplify()

void dart::BranchSimplifier::Simplify ( FlowGraph *  flow_graph )

static

Definition at line 98 of file branch_optimizer.cc.

                                                     {
  // 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());
 
      ComparisonInstr* comparison = branch->comparison();
      PhiInstr* phi = comparison->left()->definition()->AsPhi();
      ConstantInstr* constant = comparison->right()->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 comparison the same
          // deopt id that it gave the new branch.  The id should be the
          // deopt id of the original comparison.
          new_branch->comparison()->SetDeoptId(*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->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);
  }
}

ToJoinEntry()

JoinEntryInstr * dart::BranchSimplifier::ToJoinEntry ( Zone *  zone, BlockEntryInstr *  target  )

static

Definition at line 61 of file branch_optimizer.cc.

                                                                       {
  // 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;
}

ToTargetEntry()

TargetEntryInstr * dart::BranchSimplifier::ToTargetEntry ( Zone *  zone, BlockEntryInstr *  target  )

static

Definition at line 75 of file branch_optimizer.cc.

                                                                           {
  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;
}

---

The documentation for this class was generated from the following files:

• third_party/dart-lang/sdk/runtime/vm/compiler/backend/branch_optimizer.h
• third_party/dart-lang/sdk/runtime/vm/compiler/backend/branch_optimizer.cc