Detect total switches to prevent type pollution by default cases.

sdk/lib/_internal/compiler/implementation/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.
 
 part of ssa;
 
 abstract class OptimizationPhase {
   String get name;
   void visitGraph(HGraph graph);
 }
 
 class SsaOptimizerTask extends CompilerTask {
   final JavaScriptBackend backend;
   SsaOptimizerTask(JavaScriptBackend backend)
     : this.backend = backend,
       super(backend.compiler);
   String get name => 'SSA optimizer';
   Compiler get compiler => backend.compiler;
+  Map<HInstruction, Range> ranges = <HInstruction, Range>{};
 
   void runPhases(HGraph graph, List<OptimizationPhase> phases) {
     for (OptimizationPhase phase in phases) {
       runPhase(graph, phase);
     }
   }
 
   void runPhase(HGraph graph, OptimizationPhase phase) {
     phase.visitGraph(graph);
     compiler.tracer.traceGraph(phase.name, graph);
@@ skipping 30 matching lines @@
           new SsaCodeMotion(),
           new SsaLoadElimination(compiler),
           new SsaDeadPhiEliminator(),
           new SsaTypePropagator(compiler),
           new SsaValueRangeAnalyzer(compiler, constantSystem, work),
           // Previous optimizations may have generated new
           // opportunities for instruction simplification.
           new SsaInstructionSimplifier(constantSystem, backend, work),
           new SsaCheckInserter(backend, work, context.boundsChecked),
           new SsaSimplifyInterceptors(compiler, constantSystem, work),
-          dce = new SsaDeadCodeEliminator(compiler)];
+          dce = new SsaDeadCodeEliminator(compiler),
+          new SsaTypePropagator(compiler)];
       runPhases(graph, phases);
-      if (!dce.eliminatedSideEffects) return;
-      phases = <OptimizationPhase>[
-          new SsaGlobalValueNumberer(compiler),
-          new SsaCodeMotion(),
-          new SsaValueRangeAnalyzer(compiler, constantSystem, work),
-          new SsaInstructionSimplifier(constantSystem, backend, work),
-          new SsaCheckInserter(backend, work, context.boundsChecked),
-          new SsaSimplifyInterceptors(compiler, constantSystem, work),
-          new SsaDeadCodeEliminator(compiler)];
+      if (dce.eliminatedSideEffects) {
+        phases = <OptimizationPhase>[
+            new SsaGlobalValueNumberer(compiler),
+            new SsaCodeMotion(),
+            new SsaValueRangeAnalyzer(compiler, constantSystem, work),
+            new SsaInstructionSimplifier(constantSystem, backend, work),
+            new SsaCheckInserter(backend, work, context.boundsChecked),
+            new SsaSimplifyInterceptors(compiler, constantSystem, work),
+            new SsaDeadCodeEliminator(compiler)];
+      } else {
+        phases = <OptimizationPhase>[
+            // Run the simplifier to remove unneeded type checks inserted
+            // by type propagation.
+            new SsaInstructionSimplifier(constantSystem, backend, work)];
+      }
       runPhases(graph, phases);
     });
   }
 }
 
 bool isFixedLength(mask, Compiler compiler) {
   JavaScriptBackend backend = compiler.backend;
   if (mask.isContainer && mask.length != null) {
     // A container on which we have inferred the length.
     return true;
@@ skipping 844 matching lines @@
         && instruction.onlyThrowsNSM()
         && hasFollowingThrowingNSM(instruction)) {
       return true;
     }
     return !instruction.canThrow()
            && instruction is !HParameterValue
            && instruction is !HLocalSet;
   }
 
   void visitGraph(HGraph graph) {
-    analyzer = new SsaLiveBlockAnalyzer(graph);
+    analyzer = new SsaLiveBlockAnalyzer(graph, compiler);
     analyzer.analyze();
     visitPostDominatorTree(graph);
     cleanPhis(graph);
   }
 
   void visitBasicBlock(HBasicBlock block) {
     bool isDeadBlock = analyzer.isDeadBlock(block);
     block.isLive = !isDeadBlock;
     // 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;
     }
   }
 
   void cleanPhis(HGraph graph) {
     L: 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;
       // Find the index of the single live predecessor if it exists.
       int indexOfLive = -1;
       for (int i = 0; i < predecessors.length; i++) {
         if (predecessors[i].isLive) {
           if (indexOfLive >= 0) continue L;
           indexOfLive = i;
         }
       }
       // Run through the phis of the block and replace them with their input
       // that comes from the only live predecessor if that dominates the phi.
       block.forEachPhi((HPhi phi) {
         HInstruction replacement = (indexOfLive >= 0)
             ? phi.inputs[indexOfLive] : zapInstruction;
         if (replacement.dominates(phi)) {
           block.rewrite(phi, replacement);
           block.removePhi(phi);
         }
       });
     }
   }
 
+  void replaceInput(int i, HInstruction from, HInstruction by) {
+    from.inputs[i].usedBy.remove(from);
+    from.inputs[i] = by;
+    by.usedBy.add(from);
+  }
+
   void removeUsers(HInstruction instruction) {
     instruction.usedBy.forEach((user) {
       removeInput(user, instruction);
     });
     instruction.usedBy.clear();
   }
 
   void removeInput(HInstruction user, HInstruction input) {
     List<HInstruction> inputs = user.inputs;
     for (int i = 0, length = inputs.length; i < length; i++) {
       if (input == inputs[i]) {
-        HInstruction zap = zapInstruction;
-        inputs[i] = zap;
-        zap.usedBy.add(user);
+        user.inputs[i] = zapInstruction;
+        zapInstruction.usedBy.add(user);
       }
     }
   }
 }
 
 class SsaLiveBlockAnalyzer extends HBaseVisitor {
   final HGraph graph;
+  final Compiler compiler;
   final Set<HBasicBlock> live = new Set<HBasicBlock>();
   final List<HBasicBlock> worklist = <HBasicBlock>[];
-  SsaLiveBlockAnalyzer(this.graph);
+
+  SsaLiveBlockAnalyzer(this.graph, this.compiler);
+
+  JavaScriptBackend get backend => compiler.backend;
+  Map<HInstruction, Range> get ranges => backend.optimizer.ranges;
 
   bool isDeadBlock(HBasicBlock block) => !live.contains(block);
 
   void analyze() {
     markBlockLive(graph.entry);
     while (!worklist.isEmpty) {
       HBasicBlock live = worklist.removeLast();
       live.last.accept(this);
     }
   }
@@ skipping 14 matching lines @@
     if (condition.isConstant()) {
       if (condition.isConstantTrue()) {
         markBlockLive(instruction.thenBlock);
       } else {
         markBlockLive(instruction.elseBlock);
       }
     } else {
       visitControlFlow(instruction);
     }
   }
+
+  void visitSwitch(HSwitch node) {
+    if (!node.isTotal && node.expression.isInteger(compiler)) {
+      Range switchRange = ranges[node.expression];
+      if (switchRange != null &&
+          switchRange.lower is IntValue &&
+          switchRange.upper is IntValue) {
+        IntValue lowerValue = switchRange.lower;
+        IntValue upperValue = switchRange.upper;
+        int lower = lowerValue.value;
+        int upper = upperValue.value;
+        Set<int> liveLabels = new Set<int>();
+        for (int pos = 1; pos < node.inputs.length; pos++) {
+          HConstant input = node.inputs[pos];
+          if (!input.isConstantInteger()) continue;
+          IntConstant constant = input.constant;
+          int label = constant.value;
+          if (!liveLabels.contains(label) &&
+              label <= upper &&
+              label >= lower) {
+            markBlockLive(node.block.successors[pos - 1]);
+            liveLabels.add(label);
+          }
+        }
+        if (liveLabels.length != upper - lower + 1) {
+          markBlockLive(node.defaultTarget);
+        } else {
+          node.isTotal = true;
+        }
+        return;
+      }
+    }
+    visitControlFlow(node);
+  }
 }
 
 class SsaDeadPhiEliminator implements OptimizationPhase {
   final String name = "SsaDeadPhiEliminator";
 
   void visitGraph(HGraph graph) {
     final List<HPhi> worklist = <HPhi>[];
     // A set to keep track of the live phis that we found.
     final Set<HPhi> livePhis = new Set<HPhi>();
 
@@ skipping 906 matching lines @@
 
     keyedValues.forEach((receiver, values) {
       result.keyedValues[receiver] =
           new Map<HInstruction, HInstruction>.from(values);
     });
 
     result.nonEscapingReceivers.addAll(nonEscapingReceivers);
     return result;
   }
 }