dart2js: eliminate useless conditionals

pkg/compiler/lib/src/ssa/optimize.dart

 // Copyright (c) 2012, 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.
 
 import '../common/codegen.dart' show CodegenRegistry, CodegenWorkItem;
 import '../common/names.dart' show Selectors;
 import '../common/tasks.dart' show CompilerTask;
 import '../compiler.dart' show Compiler;
 import '../constants/constant_system.dart';
 import '../constants/values.dart';
@@ skipping 1441 matching lines @@
     check.inputs.add(minusOne);
     minusOne.usedBy.add(check);
   }
 }
 
 class SsaDeadCodeEliminator extends HGraphVisitor implements OptimizationPhase {
   final String name = "SsaDeadCodeEliminator";
 
   final ClosedWorld closedWorld;
   final SsaOptimizerTask optimizer;
+  HGraph _graph;
   SsaLiveBlockAnalyzer analyzer;
   Map<HInstruction, bool> trivialDeadStoreReceivers =
       new Maplet<HInstruction, bool>();
   bool eliminatedSideEffects = false;
 
   SsaDeadCodeEliminator(this.closedWorld, this.optimizer);
 
   HInstruction zapInstructionCache;
   HInstruction get zapInstruction {
     if (zapInstructionCache == null) {
@@ skipping 117 matching lines @@
         instruction.onlyThrowsNSM() &&
         hasFollowingThrowingNSM(instruction)) {
       return true;
     }
     return !instruction.canThrow() &&
         instruction is! HParameterValue &&
         instruction is! HLocalSet;
   }
 
   void visitGraph(HGraph graph) {
+    _graph = graph;
     analyzer = new SsaLiveBlockAnalyzer(graph, closedWorld, optimizer);
     analyzer.analyze();
     visitPostDominatorTree(graph);
-    cleanPhis(graph);
+    cleanPhis();
   }
 
   void visitBasicBlock(HBasicBlock block) {
     bool isDeadBlock = analyzer.isDeadBlock(block);
     block.isLive = !isDeadBlock;
+    simplifyControlFlow(block);
     // Start from the last non-control flow instruction in the block.
     HInstruction instruction = block.last.previous;
     while (instruction != null) {
       var previous = instruction.previous;
       if (isDeadBlock) {
         eliminatedSideEffects =
             eliminatedSideEffects || instruction.sideEffects.hasSideEffects();
         removeUsers(instruction);
         block.remove(instruction);
       } else if (isDeadCode(instruction)) {
         block.remove(instruction);
       }
       instruction = previous;
     }
+    block.forEachPhi(simplifyPhi);
   }
 
-  void cleanPhis(HGraph graph) {
+  void simplifyPhi(HPhi phi) {
+    // If the phi is of the form `phi(x, HTypeKnown(x))`, it does not strengthen
+    // `x`.  We can replace the phi with `x` to potentially make the HTypeKnown
+    // refinement node dead and potentially make a HIf control no HPhis.
+
+    // TODO(sra): Implement version of this test that works for a subgraph of
+    // HPhi nodes.
+    HInstruction base = null;
+    bool seenUnrefinedBase = false;
+    for (HInstruction input in phi.inputs) {
+      HInstruction value = input;
+      while (value is HTypeKnown) {
+        HTypeKnown refinement = value;
+        value = refinement.checkedInput;
+      }
+      if (value == input) seenUnrefinedBase = true;
+      base ??= value;
+      if (base != value) return;
+    }
+
+    if (seenUnrefinedBase) {
+      HBasicBlock block = phi.block;
+      block.rewrite(phi, base);
+      block.removePhi(phi);
+    }
+  }
+
+  void simplifyControlFlow(HBasicBlock block) {
+    HControlFlow instruction = block.last;
+    if (instruction is HIf) {
+      HInstruction condition = instruction.condition;
+      if (condition.isConstant()) return;
+
+      // We want to remove an if-then-else diamond when the then- and else-
+      // branches are empty and the condition does not control a HPhi. We cannot
+      // change the CFG structure so we replace the HIf condition with a
+      // constant. This may leave the original condition unused. i.e. a
+      // candidate for being dead code.
+
+      List<HBasicBlock> dominated = block.dominatedBlocks;
+      // Diamond-like control flow dominates the then-, else- and join- blocks.
+      if (dominated.length != 3) return;
+      HBasicBlock join = dominated.last;
+      if (!join.phis.isEmpty) return; // condition controls a phi.
+      // Ignore exit block - usually the join in `if (...) return ...`
+      if (join.isExitBlock()) return;
+
+      int thenSize = measureEmptyInterval(instruction.thenBlock, join);
+      if (thenSize == null) return;
+      int elseSize = measureEmptyInterval(instruction.elseBlock, join);
+      if (elseSize == null) return;
+
+      // Pick the 'live' branch to be the smallest subgraph.
+      bool value = thenSize <= elseSize;
+      HInstruction newCondition = _graph.addConstantBool(value, closedWorld);
+      instruction.inputs[0] = newCondition;
+      condition.usedBy.remove(instruction);
+      newCondition.usedBy.add(instruction);
+    }
+  }
+
+  /// Returns the number of blocks from [start] up to but not including [end].
+  /// Returns `null` if any of the blocks is non-empty (other than control
+  /// flow).  Returns `null` if there is an exit from the region other than
+  /// [end] or via control flow other than HGoto and HIf.
+  int measureEmptyInterval(HBasicBlock start, HBasicBlock end) {
+    if (start.first != start.last) return null; // start is not empty.
+    // Do a simple single-block region test first.
+    if (start.last is HGoto &&
+        start.successors.length == 1 &&
+        start.successors.single == end) {
+      return 1;
+    }
+    // TODO(sra): Implement fuller test.
+    return null;
+  }
+
+  void cleanPhis() {
     L:
-    for (HBasicBlock block in graph.blocks) {
+    for (HBasicBlock block in _graph.blocks) {
       List<HBasicBlock> predecessors = block.predecessors;
       // Zap all inputs to phis that correspond to dead blocks.
       block.forEachPhi((HPhi phi) {
         for (int i = 0; i < phi.inputs.length; ++i) {
           if (!predecessors[i].isLive && phi.inputs[i] != zapInstruction) {
             replaceInput(i, phi, zapInstruction);
           }
         }
       });
       if (predecessors.length < 2) continue L;
@@ skipping 1233 matching lines @@
 
     keyedValues.forEach((receiver, values) {
       result.keyedValues[receiver] =
           new Map<HInstruction, HInstruction>.from(values);
     });
 
     result.nonEscapingReceivers.addAll(nonEscapingReceivers);
     return result;
   }
 }