Remove useless branches in shrinking_reductions.

pkg/compiler/lib/src/cps_ir/shrinking_reductions.dart

Index: pkg/compiler/lib/src/cps_ir/shrinking_reductions.dart
diff --git a/pkg/compiler/lib/src/cps_ir/shrinking_reductions.dart b/pkg/compiler/lib/src/cps_ir/shrinking_reductions.dart
index 16a1d15f3665c4198bfe996ea8ea1b05e8b4c694..775ad1f883b9d39726be970e02c50375ba8c5c6d 100644
--- a/pkg/compiler/lib/src/cps_ir/shrinking_reductions.dart
+++ b/pkg/compiler/lib/src/cps_ir/shrinking_reductions.dart
@@ -7,6 +7,7 @@ library dart2js.cps_ir.shrinking_reductions;
 import 'cps_ir_nodes.dart';
 import 'optimizers.dart';
 import 'cps_fragment.dart';
+import '../constants/values.dart' as values;
 
 /**
  * [ShrinkingReducer] applies shrinking reductions to CPS terms as described
@@ -81,6 +82,9 @@ class ShrinkingReducer extends Pass {
       case _ReductionKind.DEAD_PARAMETER:
         _reduceDeadParameter(task);
         break;
+      case _ReductionKind.BRANCH:
+        _reduceBranch(task);
+        break;
       default:
         assert(false);
     }
@@ -191,6 +195,41 @@ class ShrinkingReducer extends Pass {
     new _RemovalVisitor(_worklist).visit(cont);
   }
 
+  void _reduceBranch(_ReductionTask task) {
+    Branch branch = task.node;
+    // Task can be added as both a useless if and a constant folding.
+    if (branch.parent == _DELETED) return;
+
+    // Replace Branch with InvokeContinuation of one of the targets. When the
+    // branch is deleted the other target becomes unreferenced and the chosen
+    // target becomes available for eta-cont and further reductions.
+    Continuation target;
+
+    Primitive condition = branch.condition.definition;
+    if (condition is Constant) {
+      values.ConstantValue value = condition.value;
+      if (value.isTrue) {

[asgerf, 2016/01/19 23:08:39]

We have a helper for non-strict branches:

isTruthyConstant(value, strict: node.isStrictCheck)

It is defined in optimizers.dart, which is sort of a random place but it's there
when we need it.

[sra1, 2016/01/20 01:03:36]

Done.

+        target = branch.trueContinuation.definition;
+      } else if (value.isFalse) {
+        target = branch.falseContinuation.definition;
+      }
+    } else if (_isBranchTargetOfUselessIf(branch.trueContinuation.definition)) {
+      target = branch.trueContinuation.definition;
+    } else {
+      return;
+    }
+
+    InvokeContinuation invoke = new InvokeContinuation(
+        target, <Primitive>[]
+        // TODO(sra): Add sourceInformation.
+        /*, sourceInformation: branch.sourceInformation*/);
+    branch.parent.body = invoke;
+    invoke.parent = branch.parent;
+    branch.parent = _DELETED;
+
+    new _RemovalVisitor(_worklist).visit(branch);
+  }
+
   void _reduceDeadParameter(_ReductionTask task) {
     // Continuation eta-reduction can destroy a dead parameter redex.  For
     // example, in the term:
@@ -371,6 +410,38 @@ bool _isEtaCont(Continuation cont) {
   return true;
 }
 
+bool _isBranchTargetOfUselessIf(Continuation cont) {
+  // A useless-if has an empty then and else branch, e.g. `if (cond);`.
+  //
+  // Detect T or F in
+  //
+  //     let cont Join() = ...
+  //       in let cont T() = Join()
+  //                   F() = Join()
+  //         in branch condition T F
+  //
+  // TODO(sra): Detect isomorphic bodies for T and F, e.g. `cond ? 1 : 1`,
+  // regardless of where the letPrim is.

[asgerf, 2016/01/19 23:08:39]

A constant pool would help here.

But there could also be an unused refinement in one of the branches, e.g if the
branch is "x == null".

(just some thoughts)

[sra1, 2016/01/20 01:03:36]

Acknowledged.

+
+  if (!cont.hasExactlyOneUse) return false;
+  if (cont.firstRef.parent is! Branch) return false;
+  Branch branch = cont.firstRef.parent;
+  Continuation trueCont = branch.trueContinuation.definition;
+  Continuation falseCont = branch.falseContinuation.definition;
+  // Are both continuations the same InvokeContinuation on a join?
+  if (trueCont.body is! InvokeContinuation) return false;
+  if (falseCont.body is! InvokeContinuation) return false;
+  InvokeContinuation trueInvoke = trueCont.body;
+  InvokeContinuation falseInvoke = falseCont.body;
+  if (trueInvoke.continuation.definition !=
+      falseInvoke.continuation.definition) {
+    return false;
+  }
+  assert(trueInvoke.arguments.length == falseInvoke.arguments.length);
+  if (trueInvoke.arguments.isNotEmpty) return false;

[asgerf, 2016/01/19 23:08:39]

We should check the arguments for equality instead of bailing out.

Is it because of the LetPrim issue? It would still catch "cond ? x : x" until we
get the constant pool.

[sra1, 2016/01/20 01:03:36]

"cond ? x : x" is a redundant phi, so I did not see it.

+  return true;
+}
+
 bool _isDeadParameter(Parameter parameter) {
   // We cannot remove function parameters as an intraprocedural optimization.
   if (parameter.parent is! Continuation || parameter.hasAtLeastOneUse) {
@@ -411,6 +482,12 @@ class _RedexVisitor extends TrampolineRecursiveVisitor {
     }
   }
 
+  void processBranch(Branch node) {
+    if (node.condition.definition is Constant) {
+      worklist.add(new _ReductionTask(_ReductionKind.BRANCH, node));
+    }
+  }
+
   void processContinuation(Continuation node) {
     // While it would be nice to remove exception handlers that are provably
     // unnecessary (e.g., the body cannot throw), that takes more sophisticated
@@ -430,6 +507,9 @@ class _RedexVisitor extends TrampolineRecursiveVisitor {
       worklist.add(new _ReductionTask(_ReductionKind.BETA_CONT_LIN, node));
     } else if (_isEtaCont(node)) {
       worklist.add(new _ReductionTask(_ReductionKind.ETA_CONT, node));
+    } else if (_isBranchTargetOfUselessIf(node)) {
+      worklist.add(new _ReductionTask(_ReductionKind.BRANCH,
+                                      node.firstRef.parent));
     }
   }
 
@@ -486,6 +566,9 @@ class _RemovalVisitor extends TrampolineRecursiveVisitor {
           worklist.add(new _ReductionTask(_ReductionKind.DEAD_CONT, cont));
         } else if (_isBetaContLin(cont)) {
           worklist.add(new _ReductionTask(_ReductionKind.BETA_CONT_LIN, cont));
+        } else if (_isBranchTargetOfUselessIf(cont)) {
+          worklist.add(
+              new _ReductionTask(_ReductionKind.BRANCH, cont.firstRef.parent));
         }
       }
     }
@@ -507,6 +590,7 @@ class _ReductionKind {
   static const _ReductionKind ETA_CONT = const _ReductionKind('eta-cont', 3);
   static const _ReductionKind DEAD_PARAMETER =
       const _ReductionKind('dead-parameter', 4);
+  static const _ReductionKind BRANCH = const _ReductionKind('branch', 5);
 
   String toString() => name;
 }