First step toward an optimizing compiler:

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 46 matching lines @@
   M(AllocateObjectWithBoundsCheck, AllocateObjectWithBoundsCheckComp)          \
   M(LoadVMField, LoadVMFieldComp)                                              \
   M(StoreVMField, StoreVMFieldComp)                                            \
   M(InstantiateTypeArguments, InstantiateTypeArgumentsComp)                    \
   M(ExtractConstructorTypeArguments, ExtractConstructorTypeArgumentsComp)      \
   M(ExtractConstructorInstantiator, ExtractConstructorInstantiatorComp)        \
   M(AllocateContext, AllocateContextComp)                                      \
   M(ChainContext, ChainContextComp)                                            \
   M(CloneContext, CloneContextComp)                                            \
   M(CatchEntry, CatchEntryComp)                                                \
+  M(BinaryOp, BinaryOpComp)                                                    \
 
 
 #define FORWARD_DECLARATION(ShortName, ClassName) class ClassName;
 FOR_EACH_COMPUTATION(FORWARD_DECLARATION)
 #undef FORWARD_DECLARATION
 
 // Forward declarations.
 class BufferFormatter;
+class Instruction;
 class Value;
 
 
 class Computation : public ZoneAllocated {
  public:
   static const int kNoCid = -1;
 
-  Computation() : cid_(-1), ic_data_(NULL), locs_(NULL) {
+  Computation() : cid_(-1), ic_data_(NULL), instr_(NULL), locs_(NULL) {
     Isolate* isolate = Isolate::Current();
     cid_ = GetNextCid(isolate);
     ic_data_ = GetICDataForCid(cid_, isolate);
   }
 
   // Unique computation/instruction id, used for deoptimization.
   intptr_t cid() const { return cid_; }
 
-  const ICData* ic_data() const { return ic_data_; }
+  ICData* ic_data() const { return ic_data_; }
+  void set_ic_data(ICData* value) { ic_data_ = value; }
 
   // Visiting support.
   virtual void Accept(FlowGraphVisitor* visitor) = 0;
 
   virtual intptr_t InputCount() const = 0;
   virtual Value* InputAt(intptr_t i) const = 0;
 
   // Static type of the computation.
   virtual RawAbstractType* StaticType() const = 0;
 
@@ skipping 10 matching lines @@
 
   // Returns structure describing location constraints required
   // to emit native code for this computation.
   LocationSummary* locs() {
     if (locs_ == NULL) {
       locs_ = MakeLocationSummary();
     }
     return locs_;
   }
 
+  // TODO(srdjan): Eliminate Instructions hierarchy. If 'use' is NULL
+  // it acts as a DoInstr, otherwise a BindInstr.
+  void set_instr(Instruction* value) { instr_ = value; }
+  Instruction* instr() const { return instr_; }
+
   // 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;
 
  private:
   friend class Instruction;
   static intptr_t GetNextCid(Isolate* isolate) {
     intptr_t tmp = isolate->computation_id();
     isolate->set_computation_id(tmp + 1);
     return tmp;
   }
   static ICData* GetICDataForCid(intptr_t cid, Isolate* isolate) {
     if (isolate->ic_data_array() == Array::null()) {
       return NULL;
     } else {
       const Array& array_handle = Array::Handle(isolate->ic_data_array());
+      if (cid >= array_handle.Length()) {
+        // For computations being added in the optimizing compiler.
+        return NULL;
+      }
       ICData& ic_data_handle = ICData::ZoneHandle();
-      if (cid < array_handle.Length()) {
-        ic_data_handle ^= array_handle.At(cid);
-      }
+      ic_data_handle ^= array_handle.At(cid);
       return &ic_data_handle;
     }
   }
 
   intptr_t cid_;
   ICData* ic_data_;
+  Instruction* instr_;
   LocationSummary* locs_;
 
   DISALLOW_COPY_AND_ASSIGN(Computation);
 };
 
 
 // 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 {
@@ skipping 79 matching lines @@
   virtual LocationSummary* MakeLocationSummary() const;                        \
   virtual void EmitNativeCode(FlowGraphCompiler* compiler);
 
 // Functions defined in all concrete value classes.
 #define DECLARE_VALUE(ShortName)                                               \
   DECLARE_COMPUTATION(ShortName)                                               \
   virtual ShortName##Val* As##ShortName() { return this; }                     \
   virtual void PrintTo(BufferFormatter* f) const;
 
 
-// Definitions and uses are mutually recursive.
-class Definition;
+class BindInstr;
 
 class UseVal : public Value {
  public:
-  explicit UseVal(Definition* definition) : definition_(definition) { }
+  explicit UseVal(BindInstr* definition) : definition_(definition) {}
 
   DECLARE_VALUE(Use)
 
-  Definition* definition() const { return definition_; }
+  BindInstr* definition() const { return definition_; }
 
  private:
-  Definition* const definition_;
+  BindInstr* definition_;
 
   DISALLOW_COPY_AND_ASSIGN(UseVal);
 };
 
 
 class ConstantVal: public Value {
  public:
   explicit ConstantVal(const Object& value)
       : value_(value) {
     ASSERT(value.IsZoneHandle());
@@ skipping 999 matching lines @@
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
  private:
   const LocalVariable& exception_var_;
   const LocalVariable& stacktrace_var_;
 
   DISALLOW_COPY_AND_ASSIGN(CatchEntryComp);
 };
 
 
+class BinaryOpComp : public TemplateComputation<2> {
+ public:
+  BinaryOpComp(Token::Kind op_kind,
+               InstanceCallComp* instance_call,
+               Value* left,
+               Value* right)
+      : op_kind_(op_kind), instance_call_(instance_call) {
+    inputs_[0] = left;
+    inputs_[1] = right;
+  }
+
+  Value* left() const { return inputs_[0]; }
+  Value* right() const { return inputs_[1]; }
+
+  Token::Kind op_kind() const { return op_kind_; }
+
+  InstanceCallComp* instance_call() const { return instance_call_; }
+
+  virtual void PrintOperandsTo(BufferFormatter* f) const;
+
+  DECLARE_COMPUTATION(BinaryOp)
+
+ private:
+  const Token::Kind op_kind_;
+  InstanceCallComp* instance_call_;
+
+  DISALLOW_COPY_AND_ASSIGN(BinaryOpComp);
+};
+
 #undef DECLARE_COMPUTATION
 
 
 // Instructions.
 //
 // <Instruction> ::= JoinEntry <Instruction>
 //                 | TargetEntry <Instruction>
 //                 | Do <Computation> <Instruction>
 //                 | Return <Value>
 //                 | Branch <Value> <Instruction> <Instruction>
@@ skipping 44 matching lines @@
   // Unique computation/instruction id, used for deoptimization, e.g. for
   // ReturnInstr, ThrowInstr and ReThrowInstr.
   intptr_t cid() const { return cid_; }
 
   const ICData* ic_data() const { return ic_data_; }
 
   virtual bool IsBlockEntry() const { return false; }
   BlockEntryInstr* AsBlockEntry() {
     return IsBlockEntry() ? reinterpret_cast<BlockEntryInstr*>(this) : NULL;
   }
-  virtual bool IsDefinition() const { return false; }
-  Definition* AsDefinition() {
-    return IsDefinition() ? reinterpret_cast<Definition*>(this) : NULL;
+  virtual bool IsBindInstr() const { return false; }
+  virtual BindInstr* AsBindInstr() {
+    return NULL;
   }
 
   virtual intptr_t InputCount() const = 0;
 
   // Visiting support.
   virtual Instruction* Accept(FlowGraphVisitor* visitor) = 0;
 
   virtual Instruction* StraightLineSuccessor() const = 0;
   virtual void SetSuccessor(Instruction* instr) = 0;
 
+  virtual void replace_computation(Computation* value) {
+    UNREACHABLE();
+  }
   // Discover basic-block structure by performing a recursive depth first
   // traversal of the instruction graph reachable from this instruction.  As
   // a side effect, the block entry instructions in the graph are assigned
   // numbers in both preorder and postorder.  The array 'preorder' maps
   // preorder block numbers to the block entry instruction with that number
   // and analogously for the array 'postorder'.  The depth first spanning
   // tree is recorded in the array 'parent', which maps preorder block
   // numbers to the preorder number of the block's spanning-tree parent.
   // The array 'assigned_vars' maps preorder block numbers to the set of
   // assigned frame-allocated local variables in the block.  As a side
@@ skipping 223 matching lines @@
   BlockEntryInstr* predecessor_;
   Instruction* successor_;
   const intptr_t try_index_;
 
   DISALLOW_COPY_AND_ASSIGN(TargetEntryInstr);
 };
 
 
 class DoInstr : public Instruction {
  public:
-  explicit DoInstr(Computation* comp)
-      : computation_(comp), successor_(NULL) { }
+  explicit DoInstr(Computation* computation)
+      : computation_(computation), successor_(NULL) {
+    ASSERT(computation != NULL);
+    computation->set_instr(this);
+  }
 
   DECLARE_INSTRUCTION(Do)
 
   Computation* computation() const { return computation_; }
+  virtual void replace_computation(Computation* value) { computation_ = value; }
 
   virtual Instruction* StraightLineSuccessor() const {
     return successor_;
   }
 
   virtual void SetSuccessor(Instruction* instr) {
     ASSERT(successor_ == NULL);
     successor_ = instr;
   }
 
   virtual void RecordAssignedVars(BitVector* assigned_vars);
 
   virtual LocationSummary* locs() const {
     return computation()->locs();
   }
 
   virtual void EmitNativeCode(FlowGraphCompiler* compiler) {
     computation()->EmitNativeCode(compiler);
   }
 
  private:
   Computation* computation_;
   Instruction* successor_;
 
   DISALLOW_COPY_AND_ASSIGN(DoInstr);
 };
 
 
-class Definition : public Instruction {
+class BindInstr : public Instruction {
  public:
-  Definition() : temp_index_(-1) { }
+  explicit BindInstr(Computation* computation)
+      : temp_index_(-1), computation_(computation), successor_(NULL) {
+    ASSERT(computation != NULL);
+    computation->set_instr(this);
+  }
 
-  virtual bool IsDefinition() const { return true; }
+  DECLARE_INSTRUCTION(Bind)
+
+  virtual bool IsBindInstr() const { return true; }
+  virtual BindInstr* AsBindInstr() { return this; }
 
   intptr_t temp_index() const { return temp_index_; }
   void set_temp_index(intptr_t index) { temp_index_ = index; }
 
- private:
-  intptr_t temp_index_;
-
-  DISALLOW_COPY_AND_ASSIGN(Definition);
-};
-
-
-class BindInstr : public Definition {
- public:
-  explicit BindInstr(Computation* computation)
-      : Definition(), computation_(computation), successor_(NULL) { }
-
-  DECLARE_INSTRUCTION(Bind)
-
   Computation* computation() const { return computation_; }
+  virtual void replace_computation(Computation* value) { computation_ = value; }
 
   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);
 
   virtual LocationSummary* locs() const {
     return computation()->locs();
   }
 
   virtual void EmitNativeCode(FlowGraphCompiler* compiler);
 
  private:
+  intptr_t temp_index_;
   Computation* computation_;
   Instruction* successor_;
 
   DISALLOW_COPY_AND_ASSIGN(BindInstr);
 };
 
 
 class ReturnInstr : public Instruction {
  public:
   ReturnInstr(intptr_t token_index, Value* value)
@@ skipping 169 matching lines @@
   const GrowableArray<BlockEntryInstr*>& block_order_;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(FlowGraphVisitor);
 };
 
 
 }  // namespace dart
 
 #endif  // VM_INTERMEDIATE_LANGUAGE_H_