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

runtime/vm/intermediate_language.h

 // 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.
 
 #ifndef VM_INTERMEDIATE_LANGUAGE_H_
 #define VM_INTERMEDIATE_LANGUAGE_H_
 
 #include "vm/allocation.h"
 #include "vm/ast.h"
 #include "vm/growable_array.h"
@@ skipping 129 matching lines @@
   virtual Value* InputAt(intptr_t i) const = 0;
   virtual void SetInputAt(intptr_t i, Value* value) = 0;
 
   // Call computations override this function and return the
   // number of pushed arguments.
   virtual intptr_t ArgumentCount() const = 0;
 
   // Returns true, if this computation can deoptimize.
   virtual bool CanDeoptimize() const  = 0;
 
-  // Static type of the computation.
-  virtual RawAbstractType* StaticType() const = 0;
+  // Compile time type of the computation.

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

Compile time type or propagated type of the computation.

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

Yes, the compile type takes the propagated types of the inputs into
consideration, but the computation itself does not cache a propagated type of
its result. The bind instruction caches the propagated type of the computation,
not the computation itself. Added comment.

+  virtual RawAbstractType* CompileType() const = 0;
 
   // Mutate assigned_vars to add the local variable index for all
   // frame-allocated locals assigned to by the computation.
   virtual void RecordAssignedVars(BitVector* assigned_vars,
                                   intptr_t fixed_parameter_count);
 
   virtual const char* DebugName() const = 0;
 
   // Printing support. These functions are sometimes overridden for custom
   // formatting. Otherwise, it prints in the format "opcode(op1, op2, op3)".
@@ skipping 14 matching lines @@
   // Create a location summary for this computation.
   // TODO(fschneider): Temporarily returns NULL for instructions
   // that are not yet converted to the location based code generation.
   virtual LocationSummary* MakeLocationSummary() const = 0;
 
   // TODO(fschneider): Make EmitNativeCode and locs const.
   virtual void EmitNativeCode(FlowGraphCompiler* compiler) = 0;
 
   static LocationSummary* MakeCallSummary();
 
-  // Declare an enum value used to define type-test predicates.
-  enum ComputationType {
-#define DECLARE_COMPUTATION_TYPE(ShortName, ClassName) k##ShortName,
+  // Declare an enum value used to define kind-test predicates.
+  enum ComputationKind {
+#define DECLARE_COMPUTATION_KIND(ShortName, ClassName) k##ShortName,
 
-  FOR_EACH_COMPUTATION(DECLARE_COMPUTATION_TYPE)
+  FOR_EACH_COMPUTATION(DECLARE_COMPUTATION_KIND)
 
-#undef DECLARE_COMPUTATION_TYPE
+#undef DECLARE_COMPUTATION_KIND
   };
 
-  virtual ComputationType computation_type() const = 0;
+  virtual ComputationKind computation_kind() const = 0;
 
   // Declare predicate for each computation.
 #define DECLARE_PREDICATE(ShortName, ClassName)                                \
   inline bool Is##ShortName() const;                                           \
   inline const ClassName* As##ShortName() const;                               \
   inline ClassName* As##ShortName();
 FOR_EACH_COMPUTATION(DECLARE_PREDICATE)
 #undef DECLARE_PREDICATE
 
  private:
@@ skipping 65 matching lines @@
 
  protected:
   EmbeddedArray<Value*, N> inputs_;
 };
 
 
 class Value : public TemplateComputation<0> {
  public:
   Value() { }
 
-  bool StaticTypeIsMoreSpecificThan(const AbstractType& dst_type) const;
+  bool CompileTypeIsMoreSpecificThan(const AbstractType& dst_type) const;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(Value);
 };
 
 
 // Functions defined in all concrete computation classes.
 #define DECLARE_COMPUTATION(ShortName)                                         \
   virtual void Accept(FlowGraphVisitor* visitor, BindInstr* instr);            \
-  virtual ComputationType computation_type() const {                           \
+  virtual ComputationKind computation_kind() const {                           \
     return Computation::k##ShortName;                                          \
   }                                                                            \
   virtual intptr_t ArgumentCount() const { return 0; }                         \
   virtual const char* DebugName() const { return #ShortName; }                 \
-  virtual RawAbstractType* StaticType() const;                                 \
+  virtual RawAbstractType* CompileType() const;                                \
   virtual LocationSummary* MakeLocationSummary() const;                        \
   virtual void EmitNativeCode(FlowGraphCompiler* compiler);
 
 // Functions defined in all concrete value classes.
 #define DECLARE_VALUE(ShortName)                                               \
   DECLARE_COMPUTATION(ShortName)                                               \
   virtual void PrintTo(BufferFormatter* f) const;
 
 
 // Function defined in all call computation classes.
 #define DECLARE_CALL_COMPUTATION(ShortName)                                    \
   virtual void Accept(FlowGraphVisitor* visitor, BindInstr* instr);            \
-  virtual ComputationType computation_type() const {                           \
+  virtual ComputationKind computation_kind() const {                           \
     return Computation::k##ShortName;                                          \
   }                                                                            \
   virtual const char* DebugName() const { return #ShortName; }                 \
-  virtual RawAbstractType* StaticType() const;                                 \
+  virtual RawAbstractType* CompileType() const;                                \
   virtual LocationSummary* MakeLocationSummary() const;                        \
   virtual void EmitNativeCode(FlowGraphCompiler* compiler);
 
 
 class Definition;
 class PhiInstr;
 
 class UseVal : public Value {
  public:
   explicit UseVal(Definition* definition) : definition_(definition) {}
@@ skipping 42 matching lines @@
   AssertAssignableComp(intptr_t token_pos,
                        intptr_t try_index,
                        Value* value,
                        Value* instantiator,
                        Value* instantiator_type_arguments,
                        const AbstractType& dst_type,
                        const String& dst_name)
       : token_pos_(token_pos),
         try_index_(try_index),
         dst_type_(dst_type),
-        dst_name_(dst_name) {
+        dst_name_(dst_name),
+        eliminated_(false) {
     ASSERT(value != NULL);
     ASSERT(instantiator != NULL);
     ASSERT(instantiator_type_arguments != NULL);
     ASSERT(!dst_type.IsNull());
     ASSERT(!dst_name.IsNull());
     inputs_[0] = value;
     inputs_[1] = instantiator;
     inputs_[2] = instantiator_type_arguments;
   }
 
   DECLARE_COMPUTATION(AssertAssignable)
 
   Value* value() const { return inputs_[0]; }
   Value* instantiator() const { return inputs_[1]; }
   Value* instantiator_type_arguments() const { return inputs_[2]; }
 
   intptr_t token_pos() const { return token_pos_; }
   intptr_t try_index() const { return try_index_; }
   const AbstractType& dst_type() const { return dst_type_; }
   const String& dst_name() const { return dst_name_; }
 
+  bool IsEliminated() const {
+    return eliminated_;
+  }
+  void Eliminate() {
+    ASSERT(!eliminated_);
+    eliminated_ = true;
+  }
+
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
   virtual bool CanDeoptimize() const { return false; }
 
  private:
   const intptr_t token_pos_;
   const intptr_t try_index_;
   const AbstractType& dst_type_;
   const String& dst_name_;
+  bool eliminated_;
 
   DISALLOW_COPY_AND_ASSIGN(AssertAssignableComp);
 };
 
 
 class AssertBooleanComp : public TemplateComputation<1> {
  public:
   AssertBooleanComp(intptr_t token_pos,
                     intptr_t try_index,
                     Value* value)
@@ skipping 1253 matching lines @@
   DISALLOW_COPY_AND_ASSIGN(ToDoubleComp);
 };
 
 
 #undef DECLARE_COMPUTATION
 
 
 // Implementation of type testers and cast functins.
 #define DEFINE_PREDICATE(ShortName, ClassName)                                 \
 bool Computation::Is##ShortName() const {                                      \
-  return computation_type() == k##ShortName;                                   \
+  return computation_kind() == k##ShortName;                                   \
 }                                                                              \
 const ClassName* Computation::As##ShortName() const {                          \
   if (!Is##ShortName()) return NULL;                                           \
   return static_cast<const ClassName*>(this);                                  \
 }                                                                              \
 ClassName* Computation::As##ShortName() {                                      \
   if (!Is##ShortName()) return NULL;                                           \
   return static_cast<ClassName*>(this);                                        \
 }
 FOR_EACH_COMPUTATION(DEFINE_PREDICATE)
@@ skipping 576 matching lines @@
   BlockEntryInstr* predecessor_;
   const intptr_t try_index_;
 
   DISALLOW_COPY_AND_ASSIGN(TargetEntryInstr);
 };
 
 
 // Abstract super-class of all instructions that define a value (Bind, Phi).
 class Definition : public Instruction {
  public:
-  Definition() : temp_index_(-1), ssa_temp_index_(-1) { }
+  Definition()
+      : temp_index_(-1),
+        ssa_temp_index_(-1),
+        propagated_type_(AbstractType::ZoneHandle()) { }

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

This could be Handle instead of ZoneHandle (propagated_type_ will not live
longer than Definition itself.

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

Done.

 
   virtual bool IsDefinition() const { return true; }
   virtual Definition* AsDefinition() { return this; }
 
   intptr_t temp_index() const { return temp_index_; }
   void set_temp_index(intptr_t index) { temp_index_ = index; }
 
   intptr_t ssa_temp_index() const { return ssa_temp_index_; }
   void set_ssa_temp_index(intptr_t index) {
     ASSERT(index >= 0);
     ssa_temp_index_ = index;
   }
   bool HasSSATemp() const { return ssa_temp_index_ >= 0; }
 
-  // Static type of the definition.
-  virtual RawAbstractType* StaticType() const = 0;
+  // Compile time type of the definition, which may be requested before type
+  // propagation during graph building.
+  virtual RawAbstractType* CompileType() const = 0;
+
+  bool HasPropagatedType() const {
+    return !propagated_type_.IsNull();
+  }
+  RawAbstractType* PropagatedType() const {
+    ASSERT(HasPropagatedType());
+    return propagated_type_.raw();
+  }

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

Add comment that it returns true if the type has changed.

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

Done.

+  bool SetPropagatedType(const AbstractType& propagated_type) {
+    if (propagated_type.IsNull()) {
+      // Not a typed definition, e.g. access to a VM field.
+      return false;
+    }
+    const bool changed =
+        propagated_type_.IsNull() || !propagated_type.Equals(propagated_type_);
+    propagated_type_ = propagated_type.raw();
+    return changed;
+  }
 
  private:
   intptr_t temp_index_;
   intptr_t ssa_temp_index_;
+  // TODO(regis): GrowableArray<const AbstractType*> propagated_types_;
+  // For now:
+  AbstractType& propagated_type_;
 
   DISALLOW_COPY_AND_ASSIGN(Definition);
 };
 
 
 Definition* UseVal::definition() const {
   // Check that the definition is either a Phi or a linked in the the IR.
   ASSERT(definition_ != NULL);
   return definition_;
 }
@@ skipping 20 matching lines @@
   void SetInputAt(intptr_t i, Value* value) {
     computation()->SetInputAt(i, value);
   }
 
   virtual bool CanDeoptimize() const { return computation()->CanDeoptimize(); }
 
   Computation* computation() const { return computation_; }
   void set_computation(Computation* value) { computation_ = value; }
   bool is_used() const { return is_used_; }
 
-  // Static type of the underlying computation.
-  virtual RawAbstractType* StaticType() const {
-    return computation()->StaticType();
-  }
+  virtual RawAbstractType* CompileType() const;
 
   virtual void RecordAssignedVars(BitVector* assigned_vars,
                                   intptr_t fixed_parameter_count);
 
   virtual LocationSummary* locs() {
     return computation()->locs();
   }
 
   virtual void EmitNativeCode(FlowGraphCompiler* compiler);
 
  private:
   Computation* computation_;
   const bool is_used_;
 
   DISALLOW_COPY_AND_ASSIGN(BindInstr);
 };
 
 
 class PhiInstr : public Definition {
  public:
   explicit PhiInstr(intptr_t num_inputs)
     : inputs_(num_inputs), is_alive_(false) {
     for (intptr_t i = 0; i < num_inputs; ++i) {
       inputs_.Add(NULL);
     }
   }
 
-  // Least upper bound of the static types of the inputs.
-  virtual RawAbstractType* StaticType() const;
+  virtual RawAbstractType* CompileType() const;
 
   virtual intptr_t ArgumentCount() const { return 0; }
 
   intptr_t InputCount() const { return inputs_.length(); }
 
   Value* InputAt(intptr_t i) const { return inputs_[i]; }
 
   void SetInputAt(intptr_t i, Value* value) { inputs_[i] = value; }
 
   virtual bool CanDeoptimize() const { return false; }
 
+  // TODO(regis): This helper will be removed once we support type sets.
+  RawAbstractType* LeastSpecificInputType() const;
+
   // Phi is alive if it reaches a non-environment use.
   bool is_alive() const { return is_alive_; }
   void mark_alive() { is_alive_ = true; }
 
   DECLARE_INSTRUCTION(Phi)
 
  private:
   GrowableArray<Value*> inputs_;
   bool is_alive_;
 
   DISALLOW_COPY_AND_ASSIGN(PhiInstr);
 };
 
 
 class ParameterInstr : public Definition {
  public:
   explicit ParameterInstr(intptr_t index) : index_(index) { }
 
   DECLARE_INSTRUCTION(Parameter)
 
   intptr_t index() const { return index_; }
 
-  // Static type of the passed-in parameter.
-  virtual RawAbstractType* StaticType() const;
+  // Compile type of the passed-in parameter.
+  virtual RawAbstractType* CompileType() const;
 
   virtual intptr_t ArgumentCount() const { return 0; }
 
   intptr_t InputCount() const { return 0; }
   Value* InputAt(intptr_t i) const {
     UNREACHABLE();
     return NULL;
   }
   void SetInputAt(intptr_t i, Value* value) { UNREACHABLE(); }
 
@@ skipping 344 matching lines @@
   const GrowableArray<BlockEntryInstr*>& block_order_;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(FlowGraphVisitor);
 };
 
 
 }  // namespace dart
 
 #endif  // VM_INTERMEDIATE_LANGUAGE_H_