Remove useless branches in shrinking_reductions.

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

 // Copyright (c) 2014, 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.
 
 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
  * in 'Compiling with Continuations, Continued' by Andrew Kennedy.
  */
 class ShrinkingReducer extends Pass {
   String get passName => 'Shrinking reductions';
 
   List<_ReductionTask> _worklist;
 
@@ skipping 54 matching lines @@
         break;
       case _ReductionKind.BETA_CONT_LIN:
         _reduceBetaContLin(task);
         break;
       case _ReductionKind.ETA_CONT:
         _reduceEtaCont(task);
         break;
       case _ReductionKind.DEAD_PARAMETER:
         _reduceDeadParameter(task);
         break;
+      case _ReductionKind.BRANCH:
+        _reduceBranch(task);
+        break;
       default:
         assert(false);
     }
   }
 
   /// Applies the dead-val reduction:
   ///   letprim x = V in E -> E (x not free in E).
   void _reduceDeadVal(_ReductionTask task) {
     assert(_isDeadVal(task.node));
 
@@ skipping 90 matching lines @@
       }
     }
 
     // Replace all occurrences with the wrapped continuation.
     cont.replaceUsesWith(wrappedCont);
 
     // Perform bookkeeping on removed body and scan for new redexes.
     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:
     //
     // let cont k0(v0) = /* v0 is not used */ in
     //   let cont k1(v1) = k0(v1) in
     //     call foo () k1
     //
     // Continuation eta-reduction of k1 gives:
     //
@@ skipping 160 matching lines @@
   // constant time by using union-find data structure.
   for (int i = 0; i < cont.parameters.length; i++) {
     if (invoke.arguments[i].definition != cont.parameters[i]) {
       return false;
     }
   }
 
   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) {
     return false;
   }
 
   // We cannot remove exception handler parameters, they have a fixed arity
   // of two.
   if (parameter.parent.parent is LetHandler) {
     return false;
@@ skipping 20 matching lines @@
   final List<_ReductionTask> worklist;
 
   _RedexVisitor(this.worklist);
 
   void processLetPrim(LetPrim node) {
     if (_isDeadVal(node)) {
       worklist.add(new _ReductionTask(_ReductionKind.DEAD_VAL, node));
     }
   }
 
+  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
     // analysis than we do in this pass.
     if (node.parent is LetHandler) return;
 
     // Continuation beta- and eta-redexes can overlap, namely when an eta-redex
     // is invoked exactly once.  We prioritize continuation beta-redexes over
     // eta-redexes because some reductions (e.g., dead parameter elimination)
     // can destroy a continuation eta-redex.  If we prioritized eta- over
     // beta-redexes, this would implicitly "create" the corresponding beta-redex
     // (in the sense that it would still apply) and the algorithm would not
     // detect it.
     if (_isDeadCont(node)) {
       worklist.add(new _ReductionTask(_ReductionKind.DEAD_CONT, node));
     } else if (_isBetaContLin(node)){
       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));
     }
   }
 
   void processParameter(Parameter node) {
     if (_isDeadParameter(node)) {
       worklist.add(new _ReductionTask(_ReductionKind.DEAD_PARAMETER, node));
     }
   }
 }
 
@@ skipping 36 matching lines @@
         if (cont.isRecursive && cont.hasAtMostOneUse) {
           // Convert recursive to nonrecursive continuations.  If the
           // continuation is still in use, it is either dead and will be
           // removed, or it is called nonrecursively outside its body.
           cont.isRecursive = false;
         }
         if (_isDeadCont(cont)) {
           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));
         }
       }
     }
   }
 }
 
 
 
 class _ReductionKind {
   final String name;
   final int hashCode;
 
   const _ReductionKind(this.name, this.hashCode);
 
   static const _ReductionKind DEAD_VAL = const _ReductionKind('dead-val', 0);
   static const _ReductionKind DEAD_CONT = const _ReductionKind('dead-cont', 1);
   static const _ReductionKind BETA_CONT_LIN =
       const _ReductionKind('beta-cont-lin', 2);
   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;
 }
 
 /// Represents a reduction task on the worklist. Implements both hashCode and
 /// operator== since instantiations are used as Set elements.
 class _ReductionTask {
   final _ReductionKind kind;
   final Node node;
 
@@ skipping 12 matching lines @@
 
   String toString() => "$kind: $node";
 }
 
 /// A dummy class used solely to mark nodes as deleted once they are removed
 /// from a term.
 class _DeletedNode extends Node {
   accept(_) {}
   setParentPointers() {}
 }