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,
+      // unless they have been zapped before.
+      block.forEachPhi((HPhi phi) {
+        for (int i = 0; i < phi.inputs.length; ++i) {
+          if (!predecessors[i].isLive &&
+              phi.inputs[i] != zapInstruction) {
+            phi.inputs[i].usedBy.remove(phi);
+            HInstruction zap = zapInstruction;

[karlklose, 2014/03/12 14:43:45]

Is this a performance optimization? I would prefer using zapInstruction
directly.

Could you create a helper and share it with the code in l. 1026-1028.

[herhut, 2014/03/13 13:27:45]

Done.

+            phi.inputs[i] = zap;
+            zap.usedBy.add(phi);
+          }
+        }
+      });
       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
@@ skipping 23 matching lines @@
         HInstruction zap = zapInstruction;
         inputs[i] = zap;
         zap.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);
+
+  Map<HInstruction, Range> get ranges =>
+      (this.compiler.backend as JavaScriptBackend).optimizer.ranges;

[karlklose, 2014/03/12 14:43:45]

If you added a 'backend' field of type JavaScriptBackend instead of the
compiler, you wouldn't need the cast here (unless you want the explicit type
check in production mode ;-)

As a bonus, the expression fits in one line.

[herhut, 2014/03/13 13:27:45]

I need the compiler, too, so I have decided to just add a getter for the backend
that has type JavaScriptBackend.

 
   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.inputs[0].isInteger(compiler)) {

[karlklose, 2014/03/12 14:43:45]

'node.inputs[0]' -> 'node.expression'.

[herhut, 2014/03/13 13:27:45]

Done.

+      Range switchRange = ranges[node.inputs[0]];

[karlklose, 2014/03/12 14:43:45]

Ditto.

[herhut, 2014/03/13 13:27:45]

Done.

+      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];
+          assert(input.isConstantInteger());

[karlklose, 2014/03/12 14:43:45]

I think this assertion is unnecessary, the code below would already  throw in
checked mode if input is of a wrong type.

[herhut, 2014/03/13 13:27:45]

You are probably right about the assert, it is a left over debugging vehicle.
The code was still wrong though, as it should not throw. Consider a switch over
integers that has some string cases, which is valid dart. I have modified the
code to not mark such cases as live.

+          IntConstant constant = input.constant;

[floitsch, 2014/03/12 16:20:25]

Pay attention that "-0.0" is a double-constant but counts as integer virtually
everywhere else.
I'm pretty sure that there are other cases where we get this wrong, though.

[herhut, 2014/03/13 13:27:45]

0.0 should be illegal in case statements (and hopefully soon will be, see
dartbug.com/17463)

+          int label = constant.value;
+          if (!liveLabels.contains(label) &&
+              (label <= upper) &&

[karlklose, 2014/03/12 14:43:45]

No need for parentheses.

[herhut, 2014/03/13 13:27:45]

I just like the visual grouping they provide. To keep with the style, I've
removed them.

+              (label >= lower)) {

[karlklose, 2014/03/12 14:43:45]

Ditto.

[herhut, 2014/03/13 13:27:45]

Done.

+            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;
   }
 }