Optimize conditional branches that have same true/false targets.

runtime/vm/flow_graph_optimizer.cc

Index: runtime/vm/flow_graph_optimizer.cc
===================================================================
--- runtime/vm/flow_graph_optimizer.cc	(revision 27294)
+++ runtime/vm/flow_graph_optimizer.cc	(working copy)
@@ -6698,6 +6698,84 @@
 }
 
 
+static bool IsEmpty(BlockEntryInstr* block) {
+  return block->next()->IsGoto()

[Kevin Millikin (Google), 2013/09/27 11:03:43]

I swear we have exactly this same function somewhere else.  Maybe in the
compiler when we do empty block elimination?

It could just be a method on the BlockEntry, I think.

[Florian Schneider, 2013/09/30 12:19:23]

We have one that deals with blocks after translated out of SSA where it checks
for parallel moves instead of phis. I could add the union of both.

[Kevin Millikin (Google), 2013/09/30 12:27:41]

Nah, it's not necessary.

+      && (!block->IsJoinEntry() || (block->AsJoinEntry()->phis() == NULL));
+}
+
+
+// Traverses a chain of empty blocks and return the first

[srdjan, 2013/09/27 15:44:11]

Why only 60 chars per line?
s/return/returns/

[Florian Schneider, 2013/09/30 12:19:23]

Done.

+// reachable non-empty block. Empty blocks are added to
+// the supplied bit vector.
+static BlockEntryInstr* FindFirstNonEmptySuccessor(
+    TargetEntryInstr* block,
+    BitVector* empty_blocks) {
+  BlockEntryInstr* current = block;
+  while (IsEmpty(current)) {
+    empty_blocks->Add(current->preorder_number());
+    current = current->next()->AsGoto()->successor();
+  }
+  return current;
+}
+
+void ConstantPropagator::RemoveRedundantBranches(FlowGraph* graph) {
+  GrowableArray<BlockEntryInstr*> ignored;
+  ConstantPropagator cp(graph, ignored);
+  cp.EliminateRedundantBranches();
+}
+
+
+void ConstantPropagator::EliminateRedundantBranches() {
+  // Canonicalize branches that have no side-effects and
+  // where true- and false-target are the same.

[srdjan, 2013/09/27 15:44:11]

s/target/targets/

[Florian Schneider, 2013/09/30 12:19:23]

Done.

+  BitVector* empty_blocks = new BitVector(graph_->preorder().length());
+  for (BlockIterator b = graph_->postorder_iterator();
+       !b.Done();
+       b.Advance()) {
+    BlockEntryInstr* block = b.Current();
+    BranchInstr* branch = block->last_instruction()->AsBranch();
+    empty_blocks->Clear();
+    if ((branch != NULL) && branch->Effects().IsNone()) {
+      ASSERT(branch->previous() != NULL);  // Not already eliminated.
+      BlockEntryInstr* if_true =
+          FindFirstNonEmptySuccessor(branch->true_successor(), empty_blocks);
+      BlockEntryInstr* if_false =
+          FindFirstNonEmptySuccessor(branch->false_successor(), empty_blocks);
+      if (if_true == if_false) {
+        // Replace the branch with a jump to the common successor.
+        // Drop the comparison, which does not have side effects
+        JoinEntryInstr* join = if_true->AsJoinEntry();
+        if (join->phis() == NULL) {
+          GotoInstr* jump = new GotoInstr(if_true->AsJoinEntry());
+          jump->InheritDeoptTarget(branch);
+
+          Instruction* previous = branch->previous();
+          branch->set_previous(NULL);
+          previous->LinkTo(jump);
+
+          // Remove uses from branch and all the empty blocks that
+          // are now unreachable.
+          branch->UnuseAllInputs();
+          for (BitVector::Iterator it(empty_blocks); !it.Done(); it.Advance()) {
+            BlockEntryInstr* empty_block = graph_->preorder()[it.Current()];
+            empty_block->UnuseAllInstructions();
+          }
+
+          if (FLAG_trace_constant_propagation) {
+            OS::Print("Eliminated branch in B%"Pd" common target B%"Pd"\n",
+                      block->block_id(), join->block_id());
+          }
+        }
+      }
+    }
+  }
+
+  graph_->DiscoverBlocks();
+  GrowableArray<BitVector*> dominance_frontier;
+  graph_->ComputeDominators(&dominance_frontier);
+}
+
+
 void ConstantPropagator::Transform() {
   if (FLAG_trace_constant_propagation) {
     OS::Print("\n==== Before constant propagation ====\n");
@@ -6715,24 +6793,16 @@
        !b.Done();
        b.Advance()) {
     BlockEntryInstr* block = b.Current();
-    JoinEntryInstr* join = block->AsJoinEntry();
     if (!reachable_->Contains(block->preorder_number())) {
       if (FLAG_trace_constant_propagation) {
         OS::Print("Unreachable B%" Pd "\n", block->block_id());
       }
       // Remove all uses in unreachable blocks.
-      if (join != NULL) {
-        for (PhiIterator it(join); !it.Done(); it.Advance()) {
-          it.Current()->UnuseAllInputs();
-        }
-      }
-      block->UnuseAllInputs();
-      for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
-        it.Current()->UnuseAllInputs();
-      }
+      block->UnuseAllInstructions();
       continue;
     }
 
+    JoinEntryInstr* join = block->AsJoinEntry();
     if (join != NULL) {
       // Remove phi inputs corresponding to unreachable predecessor blocks.
       // Predecessors will be recomputed (in block id order) after removing