Optimize conditional branches that have same true/false targets.

runtime/vm/flow_graph_optimizer.cc

 // Copyright (c) 2013, 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/flow_graph_optimizer.h"
 
 #include "vm/bit_vector.h"
 #include "vm/cha.h"
 #include "vm/dart_entry.h"
 #include "vm/flow_graph_builder.h"
@@ skipping 6680 matching lines @@
       } else {
         // No new information: Assume both targets are reachable.
         SetReachable(branch->true_successor());
         SetReachable(branch->false_successor());
       }
     }
   }
 }
 
 
+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");
     FlowGraphPrinter printer(*graph_);
     printer.PrintBlocks();
   }
 
   GrowableArray<PhiInstr*> redundant_phis(10);
 
   // We will recompute dominators, block ordering, block ids, block last
   // instructions, previous pointers, predecessors, etc. after eliminating
   // unreachable code.  We do not maintain those properties during the
   // transformation.
   for (BlockIterator b = graph_->reverse_postorder_iterator();
        !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
       // unreachable code so we merely have to keep the phi inputs in order.
       ZoneGrowableArray<PhiInstr*>* phis = join->phis();
       if ((phis != NULL) && !phis->is_empty()) {
         intptr_t pred_count = join->PredecessorCount();
         intptr_t live_count = 0;
         for (intptr_t pred_idx = 0; pred_idx < pred_count; ++pred_idx) {
           if (reachable_->Contains(
@@ skipping 737 matching lines @@
   }
 
   // Insert materializations at environment uses.
   for (intptr_t i = 0; i < exits.length(); i++) {
     CreateMaterializationAt(exits[i], alloc, alloc->cls(), *fields);
   }
 }
 
 
 }  // namespace dart