Continue work on type propagation in optimizing compiler (still WIP).

runtime/vm/intermediate_language.cc

 // 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.
 
 #include "vm/intermediate_language.h"
 
 #include "vm/bit_vector.h"
 #include "vm/dart_entry.h"
 #include "vm/flow_graph_allocator.h"
 #include "vm/flow_graph_builder.h"
@@ skipping 99 matching lines @@
   for (intptr_t i = 0; i < block_order_.length(); ++i) {
     BlockEntryInstr* entry = block_order_[i];
     entry->Accept(this);
     for (ForwardInstructionIterator it(entry); !it.Done(); it.Advance()) {
       it.Current()->Accept(this);
     }
   }
 }
 
 
-// Returns true if the static type of this value is more specific than the
+// Returns true if the compile type of this value is more specific than the
 // given dst_type.
-// TODO(regis): Should we support a set of static types?
-bool Value::StaticTypeIsMoreSpecificThan(const AbstractType& dst_type) const {
+// TODO(regis): Support a set of compile types for the given value.
+bool Value::CompileTypeIsMoreSpecificThan(const AbstractType& dst_type) const {
   ASSERT(!dst_type.IsMalformed());  // Should be tested by caller.
   ASSERT(!dst_type.IsDynamicType());  // Should be tested by caller.
   ASSERT(!dst_type.IsObjectType());  // Should be tested by caller.
 
   // If the value is the null constant, its type (NullType) is more specific
   // than the destination type, even if the destination type is the void type,
   // since a void function is allowed to return null.
   if (IsConstant() && AsConstant()->value().IsNull()) {
     return true;
   }
 
   // Functions that do not explicitly return a value, implicitly return null,
   // except generative constructors, which return the object being constructed.
   // It is therefore acceptable for void functions to return null.
   // In case of a null constant, we have already returned true above, else we
   // return false here.
   if (dst_type.IsVoidType()) {
     return false;
   }
 
-  // Consider the static type of the value.
-  const AbstractType& static_type = AbstractType::Handle(StaticType());
+  // Consider the compile type of the value.
+  const AbstractType& static_type = AbstractType::Handle(CompileType());
   ASSERT(!static_type.IsMalformed());
 
-  // If the static type of the value is void, we are type checking the result of
-  // a void function, which was checked to be null at the return statement
+  // If the compile type of the value is void, we are type checking the result
+  // of a void function, which was checked to be null at the return statement
   // inside the function.
   if (static_type.IsVoidType()) {
     return true;
   }
 
-  // If the static type of the value is NullType, the type test is eliminated.
+  // If the compile type of the value is NullType, the type test is eliminated.
   // There are only three instances that can be of Class Null:
   // Object::null(), Object::sentinel(), and Object::transition_sentinel().
   // The inline code and run time code performing the type check will never
   // encounter the 2 sentinel values. The type check of a sentinel value
   // will always be eliminated here, because these sentinel values can only
   // be encountered as constants, never as actual value of a heap object
   // being type checked.
   if (static_type.IsNullType()) {
     return true;
   }
 
   // The run time type of the value is guaranteed to be a subtype of the
-  // compile time static type of the value. However, establishing here that
-  // the static type is a subtype of the destination type does not guarantee
-  // that the run time type will also be a subtype of the destination type,
-  // because the subtype relation is not transitive.
+  // compile time type of the value. However, establishing here that
+  // the compile time type is a subtype of the destination type does not
+  // guarantee that the run time type will also be a subtype of the destination
+  // type, because the subtype relation is not transitive.
   // However, the 'more specific than' relation is transitive and is used
-  // here. In other words, if the static type of the value is more specific
+  // here. In other words, if the compile type of the value is more specific
   // than the destination type, the run time type of the value, which is
-  // guaranteed to be a subtype of the static type, is also guaranteed to be
+  // guaranteed to be a subtype of the compile type, is also guaranteed to be
   // a subtype of the destination type and the type check can therefore be
   // eliminated.
   return static_type.IsMoreSpecificThan(dst_type, NULL);
 }
 
 
-RawAbstractType* PhiInstr::StaticType() const {
-  // TODO(regis): Return the least upper bound of the input static types.
-  // It is much simpler to compute the least specific of the input static types,
-  // and it may be good enough in practice.
-  // Even better: we could keep the set of the input static types intact.
-  AbstractType& least_specific_type =
-      AbstractType::Handle(InputAt(0)->StaticType());
+RawAbstractType* PhiInstr::CompileType() const {
+  // Type propagation must have occured before requesting the compile type.
+  // Since at least one input is on a forward edge, the propagated type is set.
+  return PropagatedType();

[srdjan, 2012/08/09 22:20:53]

As discussed in chat, check if you want to split CompiledType (returns one type)
from PropagatedTypes (returns a type set/array).

[regis, 2012/08/09 23:51:37]

I will keep that question in mind for the next step introducing type sets.

+}
+
+
+RawAbstractType* PhiInstr::LeastSpecificInputType() const {
+  // To avoid cycles we consider only the propagated types of the inputs.
+  // During the first iteration of type propagation, the propagated type of
+  // inputs on back edges will not be set yet and will be ignored.
+  AbstractType& least_specific_type = AbstractType::Handle();
   AbstractType& input_type = AbstractType::Handle();
-  for (intptr_t i = 1; i < InputCount(); i++) {
-    input_type = InputAt(i)->StaticType();
-    if (input_type.IsMoreSpecificThan(least_specific_type, NULL)) {
-      // Type least_specific_type is less specific than input_type. No change.
-    } else if (least_specific_type.IsMoreSpecificThan(input_type, NULL)) {
+  for (intptr_t i = 0; i < InputCount(); i++) {
+    Value* input = InputAt(i);
+    if (input->IsUse()) {
+      if (!input->AsUse()->definition()->HasPropagatedType()) {
+        continue;
+      }
+      input_type = input->AsUse()->definition()->PropagatedType();

[srdjan, 2012/08/09 22:20:53]

input_type = input->AsUse()->CompileType();, and fix comment about cycles above.

[regis, 2012/08/09 23:51:37]

Code and comment changed:
    input_type = InputAt(i)->CompileType();

+    } else {
+      input_type = input->CompileType();
+    }
+    ASSERT(!input_type.IsNull());
+    if (least_specific_type.IsNull() ||
+        least_specific_type.IsMoreSpecificThan(input_type, NULL)) {
       // Type input_type is less specific than the current least_specific_type.
       least_specific_type = input_type.raw();
+    } else if (input_type.IsMoreSpecificThan(least_specific_type, NULL)) {
+      // Type least_specific_type is less specific than input_type. No change.
     } else {
       // The types are unrelated. No need to continue.
       least_specific_type = Type::ObjectType();
       break;
     }
   }
   return least_specific_type.raw();
 }
 
 
-RawAbstractType* ParameterInstr::StaticType() const {
-  // TODO(regis): Can type feedback provide information about the static type
-  // of a passed-in parameter?
-  // Note that in checked mode, we could return the static type of the formal
-  // parameter. However, this would be wrong if ParameterInstr is used to type
-  // check the passed-in parameter, since the type check would then always be
-  // wrongly eliminated.
+RawAbstractType* ParameterInstr::CompileType() const {
+  // TODO(regis): Can type feedback provide information about the compile type
+  // of a passed-in parameter? In that case, it would be stored in the
+  // propagated_type_ field.
+  if (HasPropagatedType()) {
+    return PropagatedType();
+  }

[srdjan, 2012/08/09 22:20:53]

How can a parameter instruction have a propagated_type ?

[regis, 2012/08/09 23:51:37]

As the TODO indicates, it would be the type obtained from type feedback and not
really a "propagated", but used similarly as one. 

+  // Note that returning the declared type of the formal parameter would be
+  // incorrect, because ParameterInstr is used as input to the type check
+  // verifying the run time type of the passed-in parameter and this check would
+  // always be wrongly eliminated.
   return Type::DynamicType();
 }
 
 
 intptr_t JoinEntryInstr::IndexOfPredecessor(BlockEntryInstr* pred) const {
   for (intptr_t i = 0; i < predecessors_.length(); ++i) {
     if (predecessors_[i] == pred) return i;
   }
   return -1;
 }
@@ skipping 13 matching lines @@
   }
 }
 
 
 void Instruction::RecordAssignedVars(BitVector* assigned_vars,
                                      intptr_t fixed_parameter_count) {
   // Nothing to do for the base class.
 }
 
 
+RawAbstractType* BindInstr::CompileType() const {
+  if (HasPropagatedType()) {
+    return PropagatedType();
+  }
+  // The compile type may be requested when building the flow graph, i.e. before
+  // type propagation has occurred.
+  return computation()->CompileType();
+}
+
+
 void BindInstr::RecordAssignedVars(BitVector* assigned_vars,
                                    intptr_t fixed_parameter_count) {
   computation()->RecordAssignedVars(assigned_vars, fixed_parameter_count);
 }
 
 
 // ==== Postorder graph traversal.
 void GraphEntryInstr::DiscoverBlocks(
     BlockEntryInstr* current_block,
     GrowableArray<BlockEntryInstr*>* preorder,
@@ skipping 206 matching lines @@
   ASSERT(index == 0);
   return successor();
 }
 
 
 void Instruction::Goto(JoinEntryInstr* entry) {
   set_next(new GotoInstr(entry));
 }
 
 
-// ==== Support for propagating static type.
-RawAbstractType* ConstantVal::StaticType() const {
+RawAbstractType* ConstantVal::CompileType() const {
+  if (value().IsNull()) {
+    return Type::NullType();
+  }
   if (value().IsInstance()) {
     return Instance::Cast(value()).GetType();
   } else {
-    UNREACHABLE();
+    ASSERT(value().IsAbstractTypeArguments());
     return AbstractType::null();
   }
 }
 
 
-RawAbstractType* UseVal::StaticType() const {
-  return definition()->StaticType();
+RawAbstractType* UseVal::CompileType() const {
+  return definition()->CompileType();
 }
 
 
-RawAbstractType* AssertAssignableComp::StaticType() const {
+RawAbstractType* AssertAssignableComp::CompileType() const {
   const AbstractType& value_static_type =
-      AbstractType::Handle(value()->StaticType());
+      AbstractType::Handle(value()->CompileType());
   if (value_static_type.IsMoreSpecificThan(dst_type(), NULL)) {
     return value_static_type.raw();
   }
   return dst_type().raw();
 }
 
 
-RawAbstractType* AssertBooleanComp::StaticType() const {
+RawAbstractType* AssertBooleanComp::CompileType() const {
   return Type::BoolInterface();
 }
 
 
-RawAbstractType* CurrentContextComp::StaticType() const {
-  UNREACHABLE();
+RawAbstractType* CurrentContextComp::CompileType() const {
   return AbstractType::null();
 }
 
 
-RawAbstractType* StoreContextComp::StaticType() const {
-  UNREACHABLE();
+RawAbstractType* StoreContextComp::CompileType() const {
   return AbstractType::null();
 }
 
 
-RawAbstractType* ClosureCallComp::StaticType() const {
-  // Because of function subtyping rules, the static return type of a closure
-  // call cannot be relied upon for static type analysis. For example, a
+RawAbstractType* ClosureCallComp::CompileType() const {
+  // Because of function subtyping rules, the declared return type of a closure
+  // call cannot be relied upon for compile type analysis. For example, a
   // function returning Dynamic can be assigned to a closure variable declared
   // to return int and may actually return a double at run-time.
   return Type::DynamicType();
 }
 
 
-RawAbstractType* InstanceCallComp::StaticType() const {
+RawAbstractType* InstanceCallComp::CompileType() const {
   // TODO(regis): Return a more specific type than Dynamic for recognized
-  // combinations of receiver static type and method name.
+  // combinations of receiver type and method name.
   return Type::DynamicType();
 }
 
 
-RawAbstractType* PolymorphicInstanceCallComp::StaticType() const {
+RawAbstractType* PolymorphicInstanceCallComp::CompileType() const {
   return Type::DynamicType();
 }
 
 
-RawAbstractType* StaticCallComp::StaticType() const {
+RawAbstractType* StaticCallComp::CompileType() const {
   return function().result_type();
 }
 
 
-RawAbstractType* LoadLocalComp::StaticType() const {
-  // TODO(regis): Verify that the type of the receiver is properly set.
+RawAbstractType* LoadLocalComp::CompileType() const {
   if (FLAG_enable_type_checks) {
     return local().type().raw();
   }
   return Type::DynamicType();
 }
 
 
-RawAbstractType* StoreLocalComp::StaticType() const {
-  return value()->StaticType();
+RawAbstractType* StoreLocalComp::CompileType() const {
+  return value()->CompileType();
 }
 
 
-RawAbstractType* StrictCompareComp::StaticType() const {
+RawAbstractType* StrictCompareComp::CompileType() const {
   return Type::BoolInterface();
 }
 
 
-RawAbstractType* EqualityCompareComp::StaticType() const {
+RawAbstractType* EqualityCompareComp::CompileType() const {
   return Type::BoolInterface();
 }
 
 
-RawAbstractType* RelationalOpComp::StaticType() const {
+RawAbstractType* RelationalOpComp::CompileType() const {
   return Type::BoolInterface();
 }
 
 
-RawAbstractType* NativeCallComp::StaticType() const {
+RawAbstractType* NativeCallComp::CompileType() const {
   // The result type of the native function is identical to the result type of
   // the enclosing native Dart function. However, we prefer to check the type
   // of the value returned from the native call.
   return Type::DynamicType();
 }
 
 
-RawAbstractType* LoadIndexedComp::StaticType() const {
+RawAbstractType* LoadIndexedComp::CompileType() const {
   return Type::DynamicType();
 }
 
 
-RawAbstractType* StoreIndexedComp::StaticType() const {
-  UNREACHABLE();
+RawAbstractType* StoreIndexedComp::CompileType() const {
   return AbstractType::null();
 }
 
 
-RawAbstractType* LoadInstanceFieldComp::StaticType() const {
+RawAbstractType* LoadInstanceFieldComp::CompileType() const {
   if (FLAG_enable_type_checks) {
     return field().type();
   }
   return Type::DynamicType();
 }
 
 
-RawAbstractType* StoreInstanceFieldComp::StaticType() const {
-  return value()->StaticType();
+RawAbstractType* StoreInstanceFieldComp::CompileType() const {
+  return value()->CompileType();
 }
 
 
-RawAbstractType* LoadStaticFieldComp::StaticType() const {
+RawAbstractType* LoadStaticFieldComp::CompileType() const {
   if (FLAG_enable_type_checks) {
     return field().type();
   }
   return Type::DynamicType();
 }
 
 
-RawAbstractType* StoreStaticFieldComp::StaticType() const {
-  return value()->StaticType();
+RawAbstractType* StoreStaticFieldComp::CompileType() const {
+  return value()->CompileType();
 }
 
 
-RawAbstractType* BooleanNegateComp::StaticType() const {
+RawAbstractType* BooleanNegateComp::CompileType() const {
   return Type::BoolInterface();
 }
 
 
-RawAbstractType* InstanceOfComp::StaticType() const {
+RawAbstractType* InstanceOfComp::CompileType() const {
   return Type::BoolInterface();
 }
 
 
-RawAbstractType* CreateArrayComp::StaticType() const {
-  UNREACHABLE();
-  return AbstractType::null();
+RawAbstractType* CreateArrayComp::CompileType() const {
+  // TODO(regis): Be more specific.
+  return Type::DynamicType();
 }
 
 
-RawAbstractType* CreateClosureComp::StaticType() const {
+RawAbstractType* CreateClosureComp::CompileType() const {
   const Function& fun = function();
   const Class& signature_class = Class::Handle(fun.signature_class());
   return signature_class.SignatureType();
 }
 
 
-RawAbstractType* AllocateObjectComp::StaticType() const {
+RawAbstractType* AllocateObjectComp::CompileType() const {
   // TODO(regis): Be more specific.
   return Type::DynamicType();
 }
 
 
-RawAbstractType* AllocateObjectWithBoundsCheckComp::StaticType() const {
-  UNREACHABLE();
+RawAbstractType* AllocateObjectWithBoundsCheckComp::CompileType() const {
+  // TODO(regis): Be more specific.
+  return Type::DynamicType();
+}
+
+
+RawAbstractType* LoadVMFieldComp::CompileType() const {
+  // Type may be null if the field is a VM field, e.g. context parent.
+  return type().raw();
+}
+
+
+RawAbstractType* StoreVMFieldComp::CompileType() const {
+  return value()->CompileType();
+}
+
+
+RawAbstractType* InstantiateTypeArgumentsComp::CompileType() const {
   return AbstractType::null();
 }
 
 
-RawAbstractType* LoadVMFieldComp::StaticType() const {
-  ASSERT(!type().IsNull());
-  return type().raw();
-}
-
-
-RawAbstractType* StoreVMFieldComp::StaticType() const {
-  return value()->StaticType();
-}
-
-
-RawAbstractType* InstantiateTypeArgumentsComp::StaticType() const {
-  UNREACHABLE();
+RawAbstractType* ExtractConstructorTypeArgumentsComp::CompileType() const {
   return AbstractType::null();
 }
 
 
-RawAbstractType* ExtractConstructorTypeArgumentsComp::StaticType() const {
-  UNREACHABLE();
+RawAbstractType* ExtractConstructorInstantiatorComp::CompileType() const {
   return AbstractType::null();
 }
 
 
-RawAbstractType* ExtractConstructorInstantiatorComp::StaticType() const {
-  UNREACHABLE();
+RawAbstractType* AllocateContextComp::CompileType() const {
   return AbstractType::null();
 }
 
 
-RawAbstractType* AllocateContextComp::StaticType() const {
-  UNREACHABLE();
+RawAbstractType* ChainContextComp::CompileType() const {
   return AbstractType::null();
 }
 
 
-RawAbstractType* ChainContextComp::StaticType() const {
-  UNREACHABLE();
+RawAbstractType* CloneContextComp::CompileType() const {
   return AbstractType::null();
 }
 
 
-RawAbstractType* CloneContextComp::StaticType() const {
-  UNREACHABLE();
+RawAbstractType* CatchEntryComp::CompileType() const {
   return AbstractType::null();
 }
 
 
-RawAbstractType* CatchEntryComp::StaticType() const {
-  UNREACHABLE();
-  return AbstractType::null();
+RawAbstractType* CheckStackOverflowComp::CompileType() const {
+  return Type::VoidType();
 }
 
 
-RawAbstractType* CheckStackOverflowComp::StaticType() const {
-  UNREACHABLE();
-  return AbstractType::null();
-}
-
-
-RawAbstractType* BinaryOpComp::StaticType() const {
+RawAbstractType* BinaryOpComp::CompileType() const {
   // TODO(srdjan): Compute based on input types (ICData).
   return Type::DynamicType();
 }
 
 
-RawAbstractType* DoubleBinaryOpComp::StaticType() const {
+RawAbstractType* DoubleBinaryOpComp::CompileType() const {
   return Type::DoubleInterface();
 }
 
 
-RawAbstractType* UnarySmiOpComp::StaticType() const {
+RawAbstractType* UnarySmiOpComp::CompileType() const {
   return Type::IntInterface();
 }
 
 
-RawAbstractType* NumberNegateComp::StaticType() const {
+RawAbstractType* NumberNegateComp::CompileType() const {
   return Type::NumberInterface();
 }
 
 
-RawAbstractType* ToDoubleComp::StaticType() const {
+RawAbstractType* ToDoubleComp::CompileType() const {
   return Type::DoubleInterface();
 }
 
 
 // Shared code generation methods (EmitNativeCode, MakeLocationSummary, and
 // PrepareEntry). Only assembly code that can be shared across all architectures
 // can be used. Machine specific register allocation and code generation
 // is located in intermediate_language_<arch>.cc
 
 
@@ skipping 282 matching lines @@
   return NULL;
 }
 
 
 void UseVal::EmitNativeCode(FlowGraphCompiler* compiler) {
   UNIMPLEMENTED();
 }
 
 
 void AssertAssignableComp::EmitNativeCode(FlowGraphCompiler* compiler) {
-  compiler->GenerateAssertAssignable(deopt_id(),
-                                     token_pos(),
-                                     try_index(),
-                                     dst_type(),
-                                     dst_name());
+  if (!IsEliminated()) {

[regis, 2012/08/09 23:51:37]

This makes sure eliminated type checks are not emitted. Do you mean something
else by "You are missing code to skip code for AssertAssignableComp if it is
eliminated"?

+    compiler->GenerateAssertAssignable(deopt_id(),
+                                       token_pos(),
+                                       try_index(),
+                                       dst_type(),
+                                       dst_name());
+  }
   ASSERT(locs()->in(0).reg() == locs()->out().reg());
 }
 
 
 LocationSummary* StoreStaticFieldComp::MakeLocationSummary() const {
   LocationSummary* locs = new LocationSummary(1, 1, LocationSummary::kNoCall);
   locs->set_in(0, Location::RequiresRegister());
   locs->set_temp(0, Location::RequiresRegister());
   locs->set_out(Location::SameAsFirstInput());
   return locs;
@@ skipping 151 matching lines @@
         locations_[i] = Location::NoLocation();
       }
     }
   }
 }
 
 
 #undef __
 
 }  // namespace dart