First shot at static type propagation and type test elimination.

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 70 matching lines @@
   // Unique computation/instruction id, used for deoptimization.
   intptr_t cid() const { return cid_; }
 
   const ICData* ic_data() const { return ic_data_; }
 
   // Visiting support.
   virtual void Accept(FlowGraphVisitor* visitor) = 0;
 
   virtual intptr_t InputCount() const = 0;
 
+  // Static type of the computation.
+  virtual RawAbstractType* StaticType() 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);
 
  private:
   friend class Instruction;
   static intptr_t GetNextCid(Isolate* isolate) {
     intptr_t tmp = isolate->computation_id();
     isolate->set_computation_id(tmp + 1);
     return tmp;
@@ skipping 18 matching lines @@
 };
 
 
 // An embedded container with N elements of type T.  Used (with partial
 // specialization for N=0) because embedded arrays cannot have size 0.
 template<typename T, intptr_t N>
 class EmbeddedArray {
  public:
   EmbeddedArray() : elements_() { }
 
-  intptr_t length() { return N; }
+  intptr_t length() const { return N; }
+  const T& operator[](intptr_t i) const {
+    ASSERT(i < length());
+    return elements_[i];
+  }
   T& operator[](intptr_t i) {
     ASSERT(i < length());
     return elements_[i];
   }
 
  private:
   T elements_[N];
 };
 
 
 template<typename T>
 class EmbeddedArray<T, 0> {
  public:
-  int length() { return 0; }
-  T& operator[](intptr_t i) {
-    UNREACHABLE();
-    static T sentinel = 0;
-    return sentinel;
-  }
+  int length() const { return 0; }
 };
 
 
 class Value;
 
 template<intptr_t N>
 class TemplateComputation : public Computation {
  public:
   virtual intptr_t InputCount() const { return N; }
 
@@ skipping 14 matching lines @@
 #undef DEFINE_TESTERS
 
  private:
   DISALLOW_COPY_AND_ASSIGN(Value);
 };
 
 
 // Functions defined in all concrete computation classes.
 #define DECLARE_COMPUTATION(ShortName)                                         \
   virtual void Accept(FlowGraphVisitor* visitor);                              \
+  virtual RawAbstractType* StaticType() const;                                 \
 
 // Functions defined in all concrete value classes.
 #define DECLARE_VALUE(ShortName)                                               \
   DECLARE_COMPUTATION(ShortName)                                               \
   virtual ShortName##Val* As##ShortName() { return this; }
 
 
 // Definitions and uses are mutually recursive.
 class Definition;
 
@@ skipping 83 matching lines @@
       : token_index_(token_index),
         try_index_(try_index) {
     ASSERT(value != NULL);
     inputs_[0] = value;
   }
 
   DECLARE_COMPUTATION(AssertBoolean)
 
   intptr_t token_index() const { return token_index_; }
   intptr_t try_index() const { return try_index_; }
-  Value* value() { return inputs_[0]; }
+  Value* value() const { return inputs_[0]; }
 
  private:
   const intptr_t token_index_;
   const intptr_t try_index_;
 
   DISALLOW_COPY_AND_ASSIGN(AssertBooleanComp);
 };
 
 
 // Denotes the current context, normally held in a register.  This is
@@ skipping 11 matching lines @@
 
 class StoreContextComp : public TemplateComputation<1> {
  public:
   explicit StoreContextComp(Value* value) {
     ASSERT(value != NULL);
     inputs_[0] = value;
   }
 
   DECLARE_COMPUTATION(StoreContext);
 
-  Value* value() { return inputs_[0]; }
+  Value* value() const { return inputs_[0]; }
 
  private:
   DISALLOW_COPY_AND_ASSIGN(StoreContextComp);
 };
 
 
 class ClosureCallComp : public Computation {
  public:
   ClosureCallComp(ClosureCallNode* node,
                   intptr_t try_index,
@@ skipping 76 matching lines @@
   StrictCompareComp(Token::Kind kind, Value* left, Value* right)
       : kind_(kind) {
     ASSERT((kind_ == Token::kEQ_STRICT) || (kind_ == Token::kNE_STRICT));
     inputs_[0] = left;
     inputs_[1] = right;
   }
 
   DECLARE_COMPUTATION(StrictCompare)
 
   Token::Kind kind() const { return kind_; }
-  Value* left() { return inputs_[0]; }
-  Value* right() { return inputs_[1]; }
+  Value* left() const { return inputs_[0]; }
+  Value* right() const { return inputs_[1]; }
 
  private:
   const Token::Kind kind_;
 
   DISALLOW_COPY_AND_ASSIGN(StrictCompareComp);
 };
 
 
 class EqualityCompareComp : public TemplateComputation<2> {
  public:
   EqualityCompareComp(intptr_t token_index,
                       intptr_t try_index,
                       Value* left,
                       Value* right)
     : token_index_(token_index),
       try_index_(try_index) {
     ASSERT(left != NULL);
     ASSERT(right != NULL);
     inputs_[0] = left;
     inputs_[1] = right;
   }
 
   DECLARE_COMPUTATION(EqualityCompareComp)
 
   intptr_t token_index() const { return token_index_; }
   intptr_t try_index() const { return try_index_; }
-  Value* left() { return inputs_[0]; }
-  Value* right() { return inputs_[1]; }
+  Value* left() const { return inputs_[0]; }
+  Value* right() const { return inputs_[1]; }
 
  private:
   const intptr_t token_index_;
   const intptr_t try_index_;
 
   DISALLOW_COPY_AND_ASSIGN(EqualityCompareComp);
 };
 
 
 class StaticCallComp : public Computation {
@@ skipping 59 matching lines @@
   StoreLocalComp(const LocalVariable& local,
                  Value* value,
                  intptr_t context_level)
       : local_(local), context_level_(context_level) {
     inputs_[0] = value;
   }
 
   DECLARE_COMPUTATION(StoreLocal)
 
   const LocalVariable& local() const { return local_; }
-  Value* value() { return inputs_[0]; }
+  Value* value() const { return inputs_[0]; }
   intptr_t context_level() const { return context_level_; }
 
   virtual void RecordAssignedVars(BitVector* assigned_vars);
 
  private:
   const LocalVariable& local_;
   const intptr_t context_level_;
 
   DISALLOW_COPY_AND_ASSIGN(StoreLocalComp);
 };
@@ skipping 36 matching lines @@
   LoadInstanceFieldComp(LoadInstanceFieldNode* ast_node, Value* instance)
       : ast_node_(*ast_node) {
     ASSERT(instance != NULL);
     inputs_[0] = instance;
   }
 
   DECLARE_COMPUTATION(LoadInstanceField)
 
   const Field& field() const { return ast_node_.field(); }
 
-  Value* instance() { return inputs_[0]; }
+  Value* instance() const { return inputs_[0]; }
 
  private:
   const LoadInstanceFieldNode& ast_node_;
 
   DISALLOW_COPY_AND_ASSIGN(LoadInstanceFieldComp);
 };
 
 
 class StoreInstanceFieldComp : public TemplateComputation<2> {
  public:
   StoreInstanceFieldComp(StoreInstanceFieldNode* ast_node,
                          Value* instance,
                          Value* value)
       : ast_node_(*ast_node) {
     ASSERT(instance != NULL);
     ASSERT(value != NULL);
     inputs_[0] = instance;
     inputs_[1] = value;
   }
 
   DECLARE_COMPUTATION(StoreInstanceField)
 
   intptr_t token_index() const { return ast_node_.token_index(); }
   const Field& field() const { return ast_node_.field(); }
 
-  Value* instance() { return inputs_[0]; }
-  Value* value() { return inputs_[1]; }
+  Value* instance() const { return inputs_[0]; }
+  Value* value() const { return inputs_[1]; }
 
  private:
   const StoreInstanceFieldNode& ast_node_;
 
   DISALLOW_COPY_AND_ASSIGN(StoreInstanceFieldComp);
 };
 
 
 class LoadStaticFieldComp : public TemplateComputation<0> {
  public:
@@ skipping 15 matching lines @@
   StoreStaticFieldComp(const Field& field, Value* value)
       : field_(field) {
     ASSERT(field.IsZoneHandle());
     ASSERT(value != NULL);
     inputs_[0] = value;
   }
 
   DECLARE_COMPUTATION(StoreStaticField);
 
   const Field& field() const { return field_; }
-  Value* value() { return inputs_[0]; }
+  Value* value() const { return inputs_[0]; }
 
  private:
   const Field& field_;
 
   DISALLOW_COPY_AND_ASSIGN(StoreStaticFieldComp);
 };
 
 
 // Not simply an InstanceCall because it has somewhat more complicated
 // semantics: the value operand is preserved before the call.
 class StoreIndexedComp : public TemplateComputation<3> {
  public:
   StoreIndexedComp(intptr_t token_index,
                    intptr_t try_index,
                    Value* array,
                    Value* index,
                    Value* value)
       : token_index_(token_index),
         try_index_(try_index) {
     inputs_[0] = array;
     inputs_[1] = index;
     inputs_[2] = value;
   }
 
   DECLARE_COMPUTATION(StoreIndexed)
 
   intptr_t token_index() const { return token_index_; }
   intptr_t try_index() const { return try_index_; }
-  Value* array() { return inputs_[0]; }
-  Value* index() { return inputs_[1]; }
-  Value* value() { return inputs_[2]; }
+  Value* array() const { return inputs_[0]; }
+  Value* index() const { return inputs_[1]; }
+  Value* value() const { return inputs_[2]; }
 
  private:
   const intptr_t token_index_;
   const intptr_t try_index_;
 
   DISALLOW_COPY_AND_ASSIGN(StoreIndexedComp);
 };
 
 
 // Not simply an InstanceCall because it has somewhat more complicated
@@ skipping 10 matching lines @@
         field_name_(field_name) {
     inputs_[0] = receiver;
     inputs_[1] = value;
   }
 
   DECLARE_COMPUTATION(InstanceSetter)
 
   intptr_t token_index() const { return token_index_; }
   intptr_t try_index() const { return try_index_; }
   const String& field_name() const { return field_name_; }
-  Value* receiver() { return inputs_[0]; }
-  Value* value() { return inputs_[1]; }
+  Value* receiver() const { return inputs_[0]; }
+  Value* value() const { return inputs_[1]; }
 
  private:
   const intptr_t token_index_;
   const intptr_t try_index_;
   const String& field_name_;
 
   DISALLOW_COPY_AND_ASSIGN(InstanceSetterComp);
 };
 
 
 // Not simply a StaticCall because it has somewhat more complicated
 // semantics: the value operand is preserved before the call.
 class StaticSetterComp : public TemplateComputation<1> {
  public:
   StaticSetterComp(intptr_t token_index,
                    intptr_t try_index,
                    const Function& setter_function,
                    Value* value)
       : token_index_(token_index),
         try_index_(try_index),
         setter_function_(setter_function) {
     inputs_[0] = value;
   }
 
   DECLARE_COMPUTATION(StaticSetter)
 
   intptr_t token_index() const { return token_index_; }
   intptr_t try_index() const { return try_index_; }
   const Function& setter_function() const { return setter_function_; }
-  Value* value() { return inputs_[0]; }
+  Value* value() const { return inputs_[0]; }
 
  private:
   const intptr_t token_index_;
   const intptr_t try_index_;
   const Function& setter_function_;
 
   DISALLOW_COPY_AND_ASSIGN(StaticSetterComp);
 };
 
 
 // Note overrideable, built-in: value? false : true.
 class BooleanNegateComp : public TemplateComputation<1> {
  public:
   explicit BooleanNegateComp(Value* value) {
     inputs_[0] = value;
   }
 
   DECLARE_COMPUTATION(BooleanNegate)
 
-  Value* value() { return inputs_[0]; }
+  Value* value() const { return inputs_[0]; }
 
  private:
   DISALLOW_COPY_AND_ASSIGN(BooleanNegateComp);
 };
 
 
 class InstanceOfComp : public Computation {
  public:
   InstanceOfComp(intptr_t token_index,
                  intptr_t try_index,
@@ skipping 149 matching lines @@
   const ClosureNode& ast_node_;
   const intptr_t try_index_;
   Value* type_arguments_;
 
   DISALLOW_COPY_AND_ASSIGN(CreateClosureComp);
 };
 
 
 class NativeLoadFieldComp : public TemplateComputation<1> {
  public:
-  NativeLoadFieldComp(Value* value, intptr_t offset_in_bytes)
-      : offset_in_bytes_(offset_in_bytes) {
+  NativeLoadFieldComp(Value* value,
+                      intptr_t offset_in_bytes,
+                      const AbstractType& type)
+      : offset_in_bytes_(offset_in_bytes), type_(type) {
     ASSERT(value != NULL);
+    ASSERT(type.IsZoneHandle());  // May be null if field is not an instance.
     inputs_[0] = value;
   }
 
   DECLARE_COMPUTATION(NativeLoadField)
 
-  Value* value() { return inputs_[0]; }
+  Value* value() const { return inputs_[0]; }
   intptr_t offset_in_bytes() const { return offset_in_bytes_; }
+  const AbstractType& type() const { return type_; }
 
  private:
   const intptr_t offset_in_bytes_;
+  const AbstractType& type_;
 
   DISALLOW_COPY_AND_ASSIGN(NativeLoadFieldComp);
 };
 
 
 class NativeStoreFieldComp : public TemplateComputation<2> {
  public:
   NativeStoreFieldComp(Value* dest, intptr_t offset_in_bytes, Value* value)
       : offset_in_bytes_(offset_in_bytes) {
     ASSERT(value != NULL);
     inputs_[0] = dest;
     inputs_[1] = value;
   }
 
   DECLARE_COMPUTATION(NativeStoreField)
 
-  Value* dest() { return inputs_[0]; }
-  Value* value() { return inputs_[1]; }
+  Value* dest() const { return inputs_[0]; }
+  Value* value() const { return inputs_[1]; }
   intptr_t offset_in_bytes() const { return offset_in_bytes_; }
 
  private:
   const intptr_t offset_in_bytes_;
 
   DISALLOW_COPY_AND_ASSIGN(NativeStoreFieldComp);
 };
 
 
 class InstantiateTypeArgumentsComp : public TemplateComputation<1> {
  public:
   InstantiateTypeArgumentsComp(intptr_t token_index,
                                intptr_t try_index,
                                const AbstractTypeArguments& type_arguments,
                                Value* instantiator)
       : token_index_(token_index),
         try_index_(try_index),
         type_arguments_(type_arguments) {
     ASSERT(instantiator != NULL);
     inputs_[0] = instantiator;
   }
 
   DECLARE_COMPUTATION(InstantiateTypeArguments)
 
-  Value* instantiator() { return inputs_[0]; }
+  Value* instantiator() const { return inputs_[0]; }
   const AbstractTypeArguments& type_arguments() const {
     return type_arguments_;
   }
   intptr_t token_index() const { return token_index_; }
   intptr_t try_index() const { return try_index_; }
 
  private:
   const intptr_t token_index_;
   const intptr_t try_index_;
   const AbstractTypeArguments& type_arguments_;
@@ skipping 11 matching lines @@
       Value* instantiator)
       : token_index_(token_index),
         try_index_(try_index),
         type_arguments_(type_arguments) {
     ASSERT(instantiator != NULL);
     inputs_[0] = instantiator;
   }
 
   DECLARE_COMPUTATION(ExtractConstructorTypeArguments)
 
-  Value* instantiator() { return inputs_[0]; }
+  Value* instantiator() const { return inputs_[0]; }
   const AbstractTypeArguments& type_arguments() const {
     return type_arguments_;
   }
   intptr_t token_index() const { return token_index_; }
   intptr_t try_index() const { return try_index_; }
 
  private:
   const intptr_t token_index_;
   const intptr_t try_index_;
   const AbstractTypeArguments& type_arguments_;
 
   DISALLOW_COPY_AND_ASSIGN(ExtractConstructorTypeArgumentsComp);
 };
 
 
 class ExtractConstructorInstantiatorComp : public TemplateComputation<1> {
  public:
   ExtractConstructorInstantiatorComp(ConstructorCallNode* ast_node,
                                      Value* instantiator)
       : ast_node_(*ast_node) {
     ASSERT(instantiator != NULL);
     inputs_[0] = instantiator;
   }
 
   DECLARE_COMPUTATION(ExtractConstructorInstantiator)
 
-  Value* instantiator() { return inputs_[0]; }
+  Value* instantiator() const { return inputs_[0]; }
   const AbstractTypeArguments& type_arguments() const {
     return ast_node_.type_arguments();
   }
   const Function& constructor() const { return ast_node_.constructor(); }
   intptr_t token_index() const { return ast_node_.token_index(); }
 
  private:
   const ConstructorCallNode& ast_node_;
 
   DISALLOW_COPY_AND_ASSIGN(ExtractConstructorInstantiatorComp);
@@ skipping 26 matching lines @@
 
 class ChainContextComp : public TemplateComputation<1> {
  public:
   explicit ChainContextComp(Value* context_value) {
     ASSERT(context_value != NULL);
     inputs_[0] = context_value;
   }
 
   DECLARE_COMPUTATION(ChainContext)
 
-  Value* context_value() { return inputs_[0]; }
+  Value* context_value() const { return inputs_[0]; }
 
  private:
   DISALLOW_COPY_AND_ASSIGN(ChainContextComp);
 };
 
 
 class CloneContextComp : public TemplateComputation<1> {
  public:
   CloneContextComp(intptr_t token_index,
                    intptr_t try_index,
                    Value* context_value)
       : token_index_(token_index),
         try_index_(try_index) {
     ASSERT(context_value != NULL);
     inputs_[0] = context_value;
   }
 
   intptr_t token_index() const { return token_index_; }
   intptr_t try_index() const { return try_index_; }
-  Value* context_value() { return inputs_[0]; }
+  Value* context_value() const { return inputs_[0]; }
 
   DECLARE_COMPUTATION(CloneContext)
 
  private:
   const intptr_t token_index_;
   const intptr_t try_index_;
 
   DISALLOW_COPY_AND_ASSIGN(CloneContextComp);
 };
 
@@ skipping 117 matching lines @@
   // Mutate assigned_vars to add the local variable index for all
   // frame-allocated locals assigned to by the instruction.
   virtual void RecordAssignedVars(BitVector* assigned_vars);
 
 #define INSTRUCTION_TYPE_CHECK(type)                                           \
   virtual bool Is##type() const { return false; }                              \
   virtual type##Instr* As##type() { return NULL; }
 FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK)
 #undef INSTRUCTION_TYPE_CHECK
 
+  // Static type of the instruction.
+  virtual RawAbstractType* StaticType() const {
+    UNREACHABLE();
+    return AbstractType::null();
+  }
+
  private:
   intptr_t cid_;
   ICData* ic_data_;
   DISALLOW_COPY_AND_ASSIGN(Instruction);
 };
 
 
 // Basic block entries are administrative nodes.  There is a distinguished
 // graph entry with no predecessor.  Joins are the only nodes with multiple
 // predecessors.  Targets are all other basic block entries.  The types
@@ skipping 220 matching lines @@
   Computation* computation() const { return computation_; }
 
   virtual Instruction* StraightLineSuccessor() const {
     return successor_;
   }
   virtual void SetSuccessor(Instruction* instr) {
     ASSERT(successor_ == NULL);
     successor_ = instr;
   }
 
+  // Static type of the underlying computation.
+  virtual RawAbstractType* StaticType() const {
+    return computation()->StaticType();
+  }
+
   virtual void RecordAssignedVars(BitVector* assigned_vars);
 
  private:
   Computation* computation_;
   Instruction* successor_;
 
   DISALLOW_COPY_AND_ASSIGN(BindInstr);
 };
 
 
@@ skipping 172 matching lines @@
   const GrowableArray<BlockEntryInstr*>& block_order_;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(FlowGraphVisitor);
 };
 
 
 }  // namespace dart
 
 #endif  // VM_INTERMEDIATE_LANGUAGE_H_