Fuse compare with branch at graph building time.

runtime/vm/intermediate_language.h

Index: runtime/vm/intermediate_language.h
===================================================================
--- runtime/vm/intermediate_language.h	(revision 9728)
+++ runtime/vm/intermediate_language.h	(working copy)
@@ -111,6 +111,7 @@
 class BindInstr;
 class BranchInstr;
 class BufferFormatter;
+class ComparisonComp;

[Kevin Millikin (Google), 2012/07/19 12:28:05]

My high level comment is that we should look for a way to get rid of the
distinction between ComparisonComp and BranchInstr.  There is some duplication
there.  Many optimizations (e.g., type specialization) will apply to both of
them.

One idea might be to get rid of ComparisonComp as test+materialize in the
instruction stream.  Instead, there are only branches, and an instruction
ToBoolean(branch) that wraps a branch to go in the instruction stream and is a
definition.

[srdjan, 2012/07/19 15:33:58]

I agree. 

 class Instruction;
 class Value;
 
@@ -163,6 +164,8 @@
     return locs_;
   }
 
+  virtual ComparisonComp* AsComparison() { return NULL; }
+
   // 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.
@@ -576,32 +579,19 @@
 
 class ComparisonComp : public TemplateComputation<2> {
  public:
-  ComparisonComp(Value* left, Value* right)
-      : fused_with_branch_(NULL) {
+  ComparisonComp(Value* left, Value* right) {
     ASSERT(left != NULL);
     ASSERT(right != NULL);
     inputs_[0] = left;
     inputs_[1] = right;
   }
 
-  void MarkFusedWithBranch(BranchInstr* branch) {
-    fused_with_branch_ = branch;
-  }
-
-  BranchInstr* fused_with_branch() const {
-    ASSERT(is_fused_with_branch());
-    return fused_with_branch_;
-  }
-
-  bool is_fused_with_branch() const {
-    return fused_with_branch_ != NULL;
-  }
-
   Value* left() const { return inputs_[0]; }
   Value* right() const { return inputs_[1]; }
 
- private:
-  BranchInstr* fused_with_branch_;
+  virtual ComparisonComp* AsComparison() { return this; }
+
+  virtual Token::Kind kind() const = 0;

[Kevin Millikin (Google), 2012/07/19 12:28:05]

I would implement this as a member variable in class ComparisonComp instead of a
virtual function.  All (existing) subclasses except EqualityCompareComp already
store it in the instance anyway.

[srdjan, 2012/07/19 15:33:58]

Done.

 };
 
 
@@ -614,7 +604,7 @@
 
   DECLARE_COMPUTATION(StrictCompare)
 
-  Token::Kind kind() const { return kind_; }
+  virtual Token::Kind kind() const { return kind_; }
 
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
@@ -646,6 +636,8 @@
   intptr_t receiver_class_id() const { return receiver_class_id_; }
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
+  virtual Token::Kind kind() const { return Token::kEQ; }
+
  private:
   const intptr_t token_pos_;
   const intptr_t try_index_;
@@ -674,7 +666,7 @@
 
   intptr_t token_pos() const { return token_pos_; }
   intptr_t try_index() const { return try_index_; }
-  Token::Kind kind() const { return kind_; }
+  virtual Token::Kind kind() const { return kind_; }
 
   // TODO(srdjan): instead of class-id pass an enum that can differentiate
   // between boxed and unboxed doubles and integers.
@@ -1740,6 +1732,9 @@
   intptr_t cid() const { return cid_; }
 
   const ICData* ic_data() const { return ic_data_; }
+  bool HasICData() const {
+    return (ic_data() != NULL) && !ic_data()->IsNull();
+  }
 
   virtual bool IsBlockEntry() const { return false; }
   BlockEntryInstr* AsBlockEntry() {
@@ -1772,6 +1767,9 @@
     // to append instruction in case of a Throw inside an expression. This
     // condition should be handled in the graph builder
     next_ = instr;
+    if ((instr != NULL) && !instr->IsBlockEntry()) {
+      instr->set_previous(this);

[Kevin Millikin (Google), 2012/07/19 12:28:05]

I see why you did this, but I think we should avoid it.  If set_next() for a
doubly-linked list has the side effect of mutating the previous field of its
argument it's error prone -- you always have to read previous of X before
calling set_next(X).

Before this change, we did not maintain previous pointers during graph
construction but computed them afterwards.  I'd be happy with maintaining them
during graph construction (still not part of set_next), but then we should also
get rid of the computation of previous poitners in BuildGraph.

[srdjan, 2012/07/19 15:33:58]

I will avoid it with the better way to construct the fused branch compare.

+    }
   }
 
   // Normal instructions can have 0 (inside a block) or 1 (last instruction in
@@ -2294,17 +2292,40 @@
 
 class BranchInstr : public InstructionWithInputs {
  public:
-  explicit BranchInstr(Value* value)
+  BranchInstr(intptr_t token_pos,

[Kevin Millikin (Google), 2012/07/19 12:28:05]

Indentation is weird.

+              intptr_t try_index,
+               Value* left,
+             Value* right,
+              Token::Kind kind)
       : InstructionWithInputs(),
-        value_(value),
+        token_pos_(token_pos),
+        try_index_(try_index),
+        left_(left),
+        right_(right),
+        kind_(kind),
         true_successor_(NULL),
-        false_successor_(NULL),
-        fused_with_comparison_(NULL),
-        is_negated_(false) { }
+        false_successor_(NULL) {
+    ASSERT(left_ != NULL);
+    ASSERT(right_ != NULL);
+    ASSERT(Token::IsEqualityOperator(kind) ||
+           Token::IsRelationalOperator(kind) ||
+           Token::IsTypeTestOperator(kind));
+  }
 
   DECLARE_INSTRUCTION(Branch)
 
-  Value* value() const { return value_; }
+  Value* left() const { return left_; }
+  Value* right() const { return right_; }
+  Token::Kind kind() const { return kind_; }
+  void set_kind(Token::Kind kind) {
+    ASSERT(Token::IsEqualityOperator(kind) ||
+           Token::IsRelationalOperator(kind) ||
+           Token::IsTypeTestOperator(kind));
+    kind_ = kind;
+  }
+  intptr_t token_pos() const { return token_pos_;}
+  intptr_t try_index() const { return try_index_; }
+
   TargetEntryInstr* true_successor() const { return true_successor_; }
   TargetEntryInstr* false_successor() const { return false_successor_; }
 
@@ -2329,22 +2350,14 @@
   void EmitBranchOnCondition(FlowGraphCompiler* compiler,
                              Condition true_condition);
 
-  void MarkFusedWithComparison(ComparisonComp* comp) {
-    fused_with_comparison_ = comp;
-  }
-
-  bool is_fused_with_comparison() const {
-    return fused_with_comparison_ != NULL;
-  }
-  bool is_negated() const { return is_negated_; }
-  void set_is_negated(bool value) { is_negated_ = value; }
-
  private:
-  Value* value_;
+  const intptr_t token_pos_;
+  const intptr_t try_index_;
+  Value* left_;
+  Value* right_;
+  Token::Kind kind_;
   TargetEntryInstr* true_successor_;
   TargetEntryInstr* false_successor_;
-  ComparisonComp* fused_with_comparison_;
-  bool is_negated_;
 
   DISALLOW_COPY_AND_ASSIGN(BranchInstr);
 };