Implement class id checks as a separate instruction and add a local CSE optimization pass.

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 83 matching lines @@
   M(AllocateContext, AllocateContextComp)                                      \
   M(ChainContext, ChainContextComp)                                            \
   M(CloneContext, CloneContextComp)                                            \
   M(CatchEntry, CatchEntryComp)                                                \
   M(BinaryOp, BinaryOpComp)                                                    \
   M(DoubleBinaryOp, DoubleBinaryOpComp)                                        \
   M(UnarySmiOp, UnarySmiOpComp)                                                \
   M(NumberNegate, NumberNegateComp)                                            \
   M(CheckStackOverflow, CheckStackOverflowComp)                                \
   M(DoubleToDouble, DoubleToDoubleComp)                                        \
-  M(SmiToDouble, SmiToDoubleComp)
+  M(SmiToDouble, SmiToDoubleComp)                                              \
+  M(CheckClass, CheckClassComp)
 
 
 #define FORWARD_DECLARATION(ShortName, ClassName) class ClassName;
 FOR_EACH_COMPUTATION(FORWARD_DECLARATION)
 #undef FORWARD_DECLARATION
 
 // Forward declarations.
 class BindInstr;
 class BranchInstr;
 class BufferFormatter;
 class ComparisonComp;
 class Definition;
 class Instruction;
 class PushArgumentInstr;
 class Value;
 
 class Computation : public ZoneAllocated {
  public:
   Computation() : deopt_id_(Isolate::kNoDeoptId), ic_data_(NULL), locs_(NULL) {
     Isolate* isolate = Isolate::Current();
     deopt_id_ = isolate->GetNextDeoptId();
     ic_data_ = isolate->GetICDataForDeoptId(deopt_id_);
   }
 
   // Unique id used for deoptimization.
   intptr_t deopt_id() const { return deopt_id_; }
 
-  ICData* ic_data() const { return ic_data_; }
-  void set_ic_data(ICData* value) { ic_data_ = value; }
+  const ICData* ic_data() const { return ic_data_; }
+  void set_ic_data(const ICData* value) { ic_data_ = value; }
   bool HasICData() const {
     return (ic_data() != NULL) && !ic_data()->IsNull();
   }
 
   // Visiting support.
   virtual void Accept(FlowGraphVisitor* visitor, BindInstr* instr) = 0;
 
   virtual intptr_t InputCount() const = 0;
   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;
 
   // Optimize this computation. Returns a replacement for the instruction
   // that wraps this computation or NULL if nothing to replace.
   virtual Definition* TryReplace(BindInstr* instr) { return NULL; }
 
+  // Functions to support CSE.

[srdjan, 2012/08/17 22:30:22]

Please document these functions briefly.

[Florian Schneider, 2012/08/20 12:09:37]

Done.

+  bool Equals(Computation* other) const;
+  virtual intptr_t Hashcode() const;
+  virtual bool AttributesEqual(Computation* other) const { return true; }
+  virtual bool HasSideEffect() const { return true; }
+
   // Compile time type of the computation, which typically depends on the
   // compile time types (and possibly propagated types) of its inputs.
   virtual RawAbstractType* CompileType() const = 0;
   virtual intptr_t ResultCid() const { return kDynamicCid; }
 
   // 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);
 
@@ skipping 41 matching lines @@
   // 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:
   intptr_t deopt_id_;
-  ICData* ic_data_;
+  const ICData* ic_data_;
   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 715 matching lines @@
   }
 
   DECLARE_COMPUTATION(LoadInstanceField)
 
   const Field& field() const { return field_; }
   Value* instance() const { return inputs_[0]; }
   const InstanceCallComp* original() const { return original_; }
 
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
   virtual bool CanDeoptimize() const { return true; }

[srdjan, 2012/08/17 22:30:22]

Should this be false if we have added a CheckClassComp in front?

[Florian Schneider, 2012/08/20 12:09:37]

Yes. I'll add a TODO to change it when we remove the old register allocator.

 
  private:
   const Field& field_;
   const InstanceCallComp* original_;  // For optimizations.
 
   DISALLOW_COPY_AND_ASSIGN(LoadInstanceFieldComp);
 };
 
 
 class StoreInstanceFieldComp : public TemplateComputation<2> {
@@ skipping 802 matching lines @@
   virtual bool CanDeoptimize() const { return true; }
   virtual intptr_t ResultCid() const { return kDoubleCid; }
 
  private:
   InstanceCallComp* instance_call_;
 
   DISALLOW_COPY_AND_ASSIGN(SmiToDoubleComp);
 };
 
 
+class CheckClassComp : public TemplateComputation<1> {

[srdjan, 2012/08/17 22:30:22]

Consider renaming it to CheckClassesComp since it checks a set of classes.

[Florian Schneider, 2012/08/20 12:09:37]

Done.

+ public:
+  CheckClassComp(Value* value, InstanceCallComp* original)
+      : original_(original) {
+    ASSERT(value != NULL);
+    inputs_[0] = value;
+  }
+
+  DECLARE_COMPUTATION(CheckClass)
+
+  virtual bool CanDeoptimize() const { return true; }
+
+  virtual bool AttributesEqual(Computation* other) const;
+
+  virtual bool HasSideEffect() const { return false; }

[srdjan, 2012/08/17 22:30:22]

Why is CheckClassComp the only computation that does not have side effect?
Please add comment.

[Florian Schneider, 2012/08/20 12:09:37]

Currently only CheckClass participates in CSE, but I added a TODO to implement
it for all computations. By default it returns the safe default (true) for now.

+
+  Value* value() const { return inputs_[0]; }
+
+  intptr_t deopt_id() const { return original_->deopt_id(); }
+  intptr_t try_index() const { return original_->try_index(); }
+
+ private:
+  InstanceCallComp* original_;
+
+  DISALLOW_COPY_AND_ASSIGN(CheckClassComp);
+};
+
+
 #undef DECLARE_COMPUTATION
 
 
 // Implementation of type testers and cast functins.
 #define DEFINE_PREDICATE(ShortName, ClassName)                                 \
 bool Computation::Is##ShortName() const {                                      \
   return computation_kind() == k##ShortName;                                   \
 }                                                                              \
 const ClassName* Computation::As##ShortName() const {                          \
   if (!Is##ShortName()) return NULL;                                           \
@@ skipping 89 matching lines @@
     ASSERT(instr == NULL || !instr->IsBlockEntry());
     // TODO(fschneider): Also add Throw and ReThrow to the list of instructions
     // that do not have a successor. Currently, the graph builder will continue
     // to append instruction in case of a Throw inside an expression. This
     // condition should be handled in the graph builder
     next_ = instr;
   }
 
   // Removed this instruction from the graph.
   Instruction* RemoveFromGraph(bool return_previous = true);
+
   // Remove value uses within this instruction and its inputs.
   virtual void RemoveInputUses() = 0;
 
+  // Insert this instruction before 'next'.
+  void InsertBefore(Instruction* next);
+
   // Normal instructions can have 0 (inside a block) or 1 (last instruction in
   // a block) successors. Branch instruction with >1 successors override this
   // function.
   virtual intptr_t SuccessorCount() const;
   virtual BlockEntryInstr* SuccessorAt(intptr_t index) const;
 
   void Goto(JoinEntryInstr* entry);
 
   // Discover basic-block structure by performing a recursive depth first
   // traversal of the instruction graph reachable from this instruction.  As
@@ skipping 598 matching lines @@
   Computation* computation() const { return computation_; }
   void set_computation(Computation* value) { computation_ = value; }
   bool is_used() const { return is_used_; }
 
   virtual RawAbstractType* CompileType() const;
   virtual intptr_t GetPropagatedCid();
 
   virtual void RecordAssignedVars(BitVector* assigned_vars,
                                   intptr_t fixed_parameter_count);
 
+  intptr_t Hashcode() const { return computation()->Hashcode(); }
+
+  bool Equals(BindInstr* other) const {
+    return computation()->Equals(other->computation());
+  }
+
   virtual LocationSummary* locs() {
     return computation()->locs();
   }
 
   virtual void EmitNativeCode(FlowGraphCompiler* compiler);
 
   virtual void RemoveInputUses() { computation()->RemoveInputUses(); }
 
  private:
   Computation* computation_;
@@ skipping 448 matching lines @@
   ForwardInstructionIterator* current_iterator_;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(FlowGraphVisitor);
 };
 
 
 }  // namespace dart
 
 #endif  // VM_INTERMEDIATE_LANGUAGE_H_