Reapply "Refactor type propagation."

lib/compiler/implementation/ssa/types.dart

Index: lib/compiler/implementation/ssa/types.dart
diff --git a/lib/compiler/implementation/ssa/types.dart b/lib/compiler/implementation/ssa/types.dart
index 563231387cfbf79165f2f6944d169644e9d8f162..d59d7be820f5ecf776d0bf70cafbb84cb06b1376 100644
--- a/lib/compiler/implementation/ssa/types.dart
+++ b/lib/compiler/implementation/ssa/types.dart
@@ -14,19 +14,21 @@ class SsaTypePropagator extends HGraphVisitor implements OptimizationPhase {
         worklist = new List<int>();
 
 
-  HType computeType(HInstruction instruction) => instruction.computeType();
+  HType computeType(HInstruction instruction) {
+    return instruction.computeTypeFromInputTypes();
+  }
 
   // Re-compute and update the type of the instruction. Returns
   // whether or not the type was changed.
   bool updateType(HInstruction instruction) {
-    if (instruction.type.isConflicting()) return false;
-    // Constants have the type they have. It can't be changed.
-    if (instruction.isConstant()) return false;
-
-    HType oldType = instruction.type;
-    HType newType = computeType(instruction);
-    instruction.type = oldType.combine(newType);
-    return oldType !== instruction.type;
+    if (instruction.propagatedType.isConflicting()) return false;
+
+    HType oldType = instruction.propagatedType;
+    HType newType = instruction.hasGuaranteedType()
+                    ? instruction.guaranteedType
+                    : computeType(instruction);
+    instruction.propagatedType = oldType.combine(newType);
+    return oldType !== instruction.propagatedType;
   }
 
   void visitGraph(HGraph graph) {
@@ -37,19 +39,24 @@ class SsaTypePropagator extends HGraphVisitor implements OptimizationPhase {
   visitBasicBlock(HBasicBlock block) {
     if (block.isLoopHeader()) {
       block.forEachPhi((HPhi phi) {
-        // Set the initial type for the phi.
-        phi.type = phi.inputs[0].type;
+        // Set the initial type for the phi. In theory we would need to mark the
+        // type of all other incoming edges as "unitialized" and take this into
+        // account when doing the propagation inside the phis. Just setting
+        // the [propagatedType] is however easier.
+        phi.propagatedType = phi.inputs[0].propagatedType;
         addToWorkList(phi);
       });
     } else {
       block.forEachPhi((HPhi phi) {
-        if (updateType(phi)) addUsersAndInputsToWorklist(phi);
+        if (updateType(phi)) addDependentInstructionsToWorkList(phi);
       });
     }
 
     HInstruction instruction = block.first;
     while (instruction !== null) {
-      if (updateType(instruction)) addUsersAndInputsToWorklist(instruction);
+      if (updateType(instruction)) {
+        addDependentInstructionsToWorkList(instruction);
+      }
       instruction = instruction.next;
     }
   }
@@ -60,17 +67,18 @@ class SsaTypePropagator extends HGraphVisitor implements OptimizationPhase {
       HInstruction instruction = workmap[id];
       assert(instruction !== null);
       workmap.remove(id);
-      if (updateType(instruction)) addUsersAndInputsToWorklist(instruction);
+      if (updateType(instruction)) {
+        addDependentInstructionsToWorkList(instruction);
+      }
     }
   }
 
-  void addUsersAndInputsToWorklist(HInstruction instruction) {
+  void addDependentInstructionsToWorkList(HInstruction instruction) {
     for (int i = 0, length = instruction.usedBy.length; i < length; i++) {
+      // The non-speculative type propagator only propagates types forward. We
+      // thus only need to add the users of the [instruction] to the list.
       addToWorkList(instruction.usedBy[i]);
-    }
-    for (int i = 0, length = instruction.inputs.length; i < length; i++) {
-      addToWorkList(instruction.inputs[i]);
-    }
+    }    
   }
 
   void addToWorkList(HInstruction instruction) {
@@ -86,11 +94,24 @@ class SsaSpeculativeTypePropagator extends SsaTypePropagator {
   final String name = 'speculative type propagator';
   SsaSpeculativeTypePropagator(Compiler compiler) : super(compiler);
 
+  void addDependentInstructionsToWorkList(HInstruction instruction) {
+    // The speculative type propagator propagates types forward and backward.
+    // Not only do we need to add the users of the [instruction] to the list.
+    // We also need to add the inputs fo the [instruction], since they might
+    // want to propagate the desired outgoing type.
+    for (int i = 0, length = instruction.usedBy.length; i < length; i++) {
+      addToWorkList(instruction.usedBy[i]);
+    }    
+    for (int i = 0, length = instruction.inputs.length; i < length; i++) {
+      addToWorkList(instruction.inputs[i]);
+    }
+  }
+
   HType computeDesiredType(HInstruction instruction) {
     HType desiredType = HType.UNKNOWN;
     for (final user in instruction.usedBy) {
       desiredType =
-          desiredType.combine(user.computeDesiredInputType(instruction));
+          desiredType.combine(user.computeDesiredTypeForInput(instruction));
       // No need to continue if two users disagree on the type.
       if (desiredType.isConflicting()) break;
     }
@@ -99,9 +120,12 @@ class SsaSpeculativeTypePropagator extends SsaTypePropagator {
 
   HType computeType(HInstruction instruction) {
     HType newType = super.computeType(instruction);
+    // [computeDesiredType] goes to all usedBys and lets them compute their
+    // desired type. By setting the [newType] here we give them more context to
+    // work with. 
+    instruction.propagatedType = newType;
     HType desiredType = computeDesiredType(instruction);
-    // If the desired type is conflicting just return the computed
-    // type.
+    // If the desired type is conflicting just return the computed type.
     if (desiredType.isConflicting()) return newType;
     return newType.combine(desiredType);
   }