Fuse compare with branch at graph building time.

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 93 matching lines @@
 
 
 #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;

[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;
 
 class Computation : public ZoneAllocated {
  public:
   static const int kNoCid = -1;
 
   Computation() : cid_(-1), ic_data_(NULL), locs_(NULL) {
     Isolate* isolate = Isolate::Current();
     cid_ = GetNextCid(isolate);
@@ skipping 32 matching lines @@
 
   // Returns structure describing location constraints required
   // to emit native code for this computation.
   LocationSummary* locs() {
     if (locs_ == NULL) {
       locs_ = MakeLocationSummary();
     }
     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.
   virtual LocationSummary* MakeLocationSummary() const = 0;
 
   // TODO(fschneider): Make EmitNativeCode and locs const.
   virtual void EmitNativeCode(FlowGraphCompiler* compiler) = 0;
 
   static LocationSummary* MakeCallSummary();
 
@@ skipping 393 matching lines @@
 
  private:
   InstanceCallComp* instance_call_;
 
   DISALLOW_COPY_AND_ASSIGN(PolymorphicInstanceCallComp);
 };
 
 
 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.

 };
 
 
 class StrictCompareComp : public ComparisonComp {
  public:
   StrictCompareComp(Token::Kind kind, Value* left, Value* right)
       : ComparisonComp(left, right), kind_(kind) {
     ASSERT((kind_ == Token::kEQ_STRICT) || (kind_ == Token::kNE_STRICT));
   }
 
   DECLARE_COMPUTATION(StrictCompare)
 
-  Token::Kind kind() const { return kind_; }
+  virtual Token::Kind kind() const { return kind_; }
 
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
  private:
   const Token::Kind kind_;
 
   DISALLOW_COPY_AND_ASSIGN(StrictCompareComp);
 };
 
 
@@ skipping 11 matching lines @@
 
   DECLARE_COMPUTATION(EqualityCompare)
 
   intptr_t token_pos() const { return token_pos_; }
   intptr_t try_index() const { return try_index_; }
 
   void set_receiver_class_id(intptr_t value) { receiver_class_id_ = value; }
   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_;
   intptr_t receiver_class_id_;  // Set by optimizer.
 
   DISALLOW_COPY_AND_ASSIGN(EqualityCompareComp);
 };
 
 
 class RelationalOpComp : public ComparisonComp {
  public:
   RelationalOpComp(intptr_t token_pos,
                    intptr_t try_index,
                    Token::Kind kind,
                    Value* left,
                    Value* right)
       : ComparisonComp(left, right),
         token_pos_(token_pos),
         try_index_(try_index),
         kind_(kind),
         operands_class_id_(kObject) {
     ASSERT(Token::IsRelationalOperator(kind));
   }
 
   DECLARE_COMPUTATION(RelationalOp)
 
   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.
   void set_operands_class_id(intptr_t value) {
     operands_class_id_ = value;
   }
 
   intptr_t operands_class_id() const { return operands_class_id_; }
 
   virtual void PrintOperandsTo(BufferFormatter* f) const;
@@ skipping 1045 matching lines @@
     Isolate* isolate = Isolate::Current();
     cid_ = Computation::GetNextCid(isolate);
     ic_data_ = Computation::GetICDataForCid(cid_, isolate);
   }
 
   // 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_; }
+  bool HasICData() const {
+    return (ic_data() != NULL) && !ic_data()->IsNull();
+  }
 
   virtual bool IsBlockEntry() const { return false; }
   BlockEntryInstr* AsBlockEntry() {
     return IsBlockEntry() ? reinterpret_cast<BlockEntryInstr*>(this) : NULL;
   }
   virtual bool IsDefinition() const { return false; }
   virtual Definition* AsDefinition() { return NULL; }
 
   virtual intptr_t InputCount() const = 0;
   virtual Value* InputAt(intptr_t i) const = 0;
@@ skipping 12 matching lines @@
   void set_next(Instruction* instr) {
     ASSERT(!IsGraphEntry());
     ASSERT(!IsReturn());
     ASSERT(!IsBranch());
     ASSERT(!IsPhi());
     // 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;
+    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
   // a block) successors. Branch instruction with >1 successors override this
   // function.
   virtual intptr_t SuccessorCount() const;
   virtual BlockEntryInstr* SuccessorAt(intptr_t index) const;
 
   // Discover basic-block structure by performing a recursive depth first
   // traversal of the instruction graph reachable from this instruction.  As
@@ skipping 502 matching lines @@
   const intptr_t try_index_;
   Value* exception_;
   Value* stack_trace_;
 
   DISALLOW_COPY_AND_ASSIGN(ReThrowInstr);
 };
 
 
 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_; }
 
   TargetEntryInstr** true_successor_address() { return &true_successor_; }
   TargetEntryInstr** false_successor_address() { return &false_successor_; }
 
   virtual intptr_t SuccessorCount() const;
   virtual BlockEntryInstr* SuccessorAt(intptr_t index) const;
 
   virtual void DiscoverBlocks(
       BlockEntryInstr* current_block,
       GrowableArray<BlockEntryInstr*>* preorder,
       GrowableArray<BlockEntryInstr*>* postorder,
       GrowableArray<intptr_t>* parent,
       GrowableArray<BitVector*>* assigned_vars,
       intptr_t variable_count);
 
   virtual LocationSummary* MakeLocationSummary() const;
 
   virtual void EmitNativeCode(FlowGraphCompiler* compiler);
 
   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);
 };
 
 
 // This class is often passed by value. Add additional fields with caution.
 class MoveOperands : public ValueObject {
  public:
   MoveOperands(Location dest, Location src) : dest_(dest), src_(src) { }
 
@@ skipping 132 matching lines @@
   const GrowableArray<BlockEntryInstr*>& block_order_;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(FlowGraphVisitor);
 };
 
 
 }  // namespace dart
 
 #endif  // VM_INTERMEDIATE_LANGUAGE_H_