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/cpu.h"
 #include "vm/dart_entry.h"
@@ skipping 7151 matching lines @@
   cp.Transform();
 }
 
 
 void ConstantPropagator::OptimizeBranches(FlowGraph* graph) {
   GrowableArray<BlockEntryInstr*> ignored;
   ConstantPropagator cp(graph, ignored);
   cp.Analyze();
   cp.VisitBranches();
   cp.Transform();
+  cp.EliminateRedundantBranches();
 }
 
 
 void ConstantPropagator::SetReachable(BlockEntryInstr* block) {
   if (!reachable_->Contains(block->preorder_number())) {
     reachable_->Add(block->preorder_number());
     block_worklist_.Add(block);
   }
 }
 
@@ skipping 1254 matching lines @@
       } else {
         // No new information: Assume both targets are reachable.
         SetReachable(branch->true_successor());
         SetReachable(branch->false_successor());
       }
     }
   }
 }
 
 
+static bool IsEmptyBlock(BlockEntryInstr* block) {
+  return block->next()->IsGoto() &&
+      (!block->IsJoinEntry() || (block->AsJoinEntry()->phis() == NULL));
+}
+
+
+// Traverses a chain of empty blocks and returns the first reachable non-empty
+// block that is not dominated by the start block. The empty blocks are added
+// to the supplied bit vector.
+static BlockEntryInstr* FindFirstNonEmptySuccessor(
+    TargetEntryInstr* block,
+    BitVector* empty_blocks) {
+  BlockEntryInstr* current = block;
+  while (IsEmptyBlock(current) && block->Dominates(current)) {
+    ASSERT(!block->IsJoinEntry() || (block->AsJoinEntry()->phis() == NULL));
+    empty_blocks->Add(current->preorder_number());
+    current = current->next()->AsGoto()->successor();
+  }
+  return current;
+}
+
+
+void ConstantPropagator::EliminateRedundantBranches() {
+  // Canonicalize branches that have no side-effects and where true- and
+  // false-targets are the same.
+  bool changed = false;
+  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->ClearAllInstructions();
+          }
+
+          changed = true;
+
+          if (FLAG_trace_constant_propagation) {
+            OS::Print("Eliminated branch in B%"Pd" common target B%"Pd"\n",
+                      block->block_id(), join->block_id());
+          }
+        }
+      }
+    }
+  }
+
+  if (changed) {

[Vyacheslav Egorov (Google), 2014/05/01 22:57:05]

Maybe we should update the dominator tree in place? All blocks we are removing
are dominated by a single block so it's just boils down to removing subtree.

[Florian Schneider, 2014/05/01 23:11:35]

I'll add a TODO for now.

+    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->ClearAllInstructions();
       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 713 matching lines @@
   }
 
   // Insert materializations at environment uses.
   for (intptr_t i = 0; i < exits.length(); i++) {
     CreateMaterializationAt(exits[i], alloc, alloc->cls(), *slots);
   }
 }
 
 
 }  // namespace dart