Generalize if-conversion to arbitrary smi comparisons.

runtime/vm/intermediate_language.h

 // Copyright (c) 2013, 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 2132 matching lines @@
       locs_ = MakeLocationSummary();
     }
     return locs_;
   }
 
  protected:
   EmbeddedArray<Value*, N> inputs_;
 
  private:
   friend class BranchInstr;
+  friend class IfThenElseInstr;
 
   virtual void RawSetInputAt(intptr_t i, Value* value) {
     inputs_[i] = value;
   }
 
   LocationSummary* locs_;
 };
 
 
+struct BranchLabels {
+  Label* true_label;
+  Label* false_label;
+  Label* fall_through;
+};
+
+
 class ComparisonInstr : public TemplateDefinition<2> {
  public:
   Value* left() const { return inputs_[0]; }
   Value* right() const { return inputs_[1]; }
 
   virtual ComparisonInstr* AsComparison() { return this; }
 
   intptr_t token_pos() const { return token_pos_; }
   Token::Kind kind() const { return kind_; }
 
+  virtual ComparisonInstr* CopyWithNewOperands(Value* left, Value* right) = 0;
+
   virtual void EmitBranchCode(FlowGraphCompiler* compiler,
                               BranchInstr* branch) = 0;
 
+  virtual Condition EmitComparisonCode(FlowGraphCompiler* compiler,
+                                       BranchLabels labels) = 0;
+
   void SetDeoptId(intptr_t deopt_id) {
     deopt_id_ = deopt_id;
   }
 
   // Operation class id is computed from collected ICData.
   void set_operation_cid(intptr_t value) { operation_cid_ = value; }
   intptr_t operation_cid() const { return operation_cid_; }
 
   void NegateComparison() {
     kind_ = Token::NegateComparison(kind_);
@@ skipping 13 matching lines @@
   const intptr_t token_pos_;
   Token::Kind kind_;
   intptr_t operation_cid_;  // Set by optimizer.
 
   DISALLOW_COPY_AND_ASSIGN(ComparisonInstr);
 };
 
 
 class BranchInstr : public Instruction {
  public:
-  explicit BranchInstr(ComparisonInstr* comparison, bool is_checked = false);
+  explicit BranchInstr(ComparisonInstr* comparison, bool is_checked = false)
+      : comparison_(comparison),
+        is_checked_(is_checked),
+        constrained_type_(NULL),
+        constant_target_(NULL) {
+    ASSERT(comparison->env() == NULL);
+    for (intptr_t i = comparison->InputCount() - 1; i >= 0; --i) {
+      comparison->InputAt(i)->set_instruction(this);
+    }
+  }
 
   DECLARE_INSTRUCTION(Branch)
 
   virtual intptr_t ArgumentCount() const {
     return comparison()->ArgumentCount();
   }
 
   intptr_t InputCount() const { return comparison()->InputCount(); }
 
   Value* InputAt(intptr_t i) const { return comparison()->InputAt(i); }
@@ skipping 15 matching lines @@
   ComparisonInstr* comparison() const { return comparison_; }
   void SetComparison(ComparisonInstr* comp);
 
   bool is_checked() const { return is_checked_; }
 
   virtual LocationSummary* locs() {
     if (comparison()->locs_ == NULL) {
       LocationSummary* summary = comparison()->MakeLocationSummary();
       // Branches don't produce a result.
       summary->set_out(Location::NoLocation());
+      // The back-end expects the location summary to be stored in the
+      // comparison.
       comparison()->locs_ = summary;
     }
     return comparison()->locs_;
   }
 
   virtual intptr_t DeoptimizationTarget() const {
     return comparison()->DeoptimizationTarget();
   }
 
   virtual Representation RequiredInputRepresentation(intptr_t i) const {
@@ skipping 33 matching lines @@
   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;
 
  private:
-  virtual void RawSetInputAt(intptr_t i, Value* value);
+  virtual void RawSetInputAt(intptr_t i, Value* value) {
+    comparison()->RawSetInputAt(i, value);
+  }
 
   TargetEntryInstr* true_successor_;
   TargetEntryInstr* false_successor_;
   ComparisonInstr* comparison_;
   const bool is_checked_;
   ConstrainedCompileType* constrained_type_;
   TargetEntryInstr* constant_target_;
 
   DISALLOW_COPY_AND_ASSIGN(BranchInstr);
 };
@@ skipping 571 matching lines @@
 
   DISALLOW_COPY_AND_ASSIGN(PolymorphicInstanceCallInstr);
 };
 
 
 class StrictCompareInstr : public ComparisonInstr {
  public:
   StrictCompareInstr(intptr_t token_pos,
                      Token::Kind kind,
                      Value* left,
-                     Value* right);
+                     Value* right,
+                     bool needs_number_check);
 
   DECLARE_INSTRUCTION(StrictCompare)
+
+  virtual ComparisonInstr* CopyWithNewOperands(Value* left, Value* right);
+
   virtual CompileType ComputeType() const;
 
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
   virtual bool CanBecomeDeoptimizationTarget() const {
     // StrictCompare can be merged into Branch and thus needs an environment.
     return true;
   }
 
   virtual bool CanDeoptimize() const { return false; }
 
   virtual Definition* Canonicalize(FlowGraph* flow_graph);
 
   virtual void EmitBranchCode(FlowGraphCompiler* compiler,
                               BranchInstr* branch);
 
+  virtual Condition EmitComparisonCode(FlowGraphCompiler* compiler,
+                                       BranchLabels labels);
+
   bool needs_number_check() const { return needs_number_check_; }
   void set_needs_number_check(bool value) { needs_number_check_ = value; }
 
   virtual bool AllowsCSE() const { return true; }
   virtual EffectSet Effects() const { return EffectSet::None(); }
   virtual EffectSet Dependencies() const { return EffectSet::None(); }
   virtual bool AttributesEqual(Instruction* other) const;
 
   virtual bool MayThrow() const { return false; }
 
  private:
   // True if the comparison must check for double, Mint or Bigint and
   // use value comparison instead.
   bool needs_number_check_;
 
   DISALLOW_COPY_AND_ASSIGN(StrictCompareInstr);
 };
 
 
 // Comparison instruction that is equivalent to the (left & right) == 0
 // comparison pattern.
 class TestSmiInstr : public ComparisonInstr {
  public:
   TestSmiInstr(intptr_t token_pos, Token::Kind kind, Value* left, Value* right)
       : ComparisonInstr(token_pos, kind, left, right) {
     ASSERT(kind == Token::kEQ || kind == Token::kNE);
   }
 
   DECLARE_INSTRUCTION(TestSmi);
+
+  virtual ComparisonInstr* CopyWithNewOperands(Value* left, Value* right);
+
   virtual CompileType ComputeType() const;
 
   virtual bool CanDeoptimize() const { return false; }
 
   virtual bool CanBecomeDeoptimizationTarget() const {
     // TestSmi can be merged into Branch and thus needs an environment.
     return true;
   }
 
   virtual intptr_t DeoptimizationTarget() const {
     return GetDeoptId();
   }
 
   virtual Representation RequiredInputRepresentation(intptr_t idx) const {
     return kTagged;
   }
 
   virtual EffectSet Effects() const { return EffectSet::None(); }
 
   virtual bool MayThrow() const { return false; }
 
   virtual void EmitBranchCode(FlowGraphCompiler* compiler,
                               BranchInstr* branch);
 
+  virtual Condition EmitComparisonCode(FlowGraphCompiler* compiler,
+                                       BranchLabels labels);
+
  private:
   DISALLOW_COPY_AND_ASSIGN(TestSmiInstr);
 };
 
 
 class EqualityCompareInstr : public ComparisonInstr {
  public:
   EqualityCompareInstr(intptr_t token_pos,
                        Token::Kind kind,
                        Value* left,
                        Value* right,
                        intptr_t cid,
                        intptr_t deopt_id)
       : ComparisonInstr(token_pos, kind, left, right) {
     ASSERT(Token::IsEqualityOperator(kind));
     set_operation_cid(cid);
     deopt_id_ = deopt_id;  // Override generated deopt-id.
   }
 
   DECLARE_INSTRUCTION(EqualityCompare)
+
+  virtual ComparisonInstr* CopyWithNewOperands(Value* left, Value* right);
+
   virtual CompileType ComputeType() const;
 
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
   virtual bool CanDeoptimize() const { return false; }
 
   virtual bool CanBecomeDeoptimizationTarget() const {
     // EqualityCompare can be merged into Branch and thus needs an environment.
     return true;
   }
 
   virtual void EmitBranchCode(FlowGraphCompiler* compiler,
                               BranchInstr* branch);
 
+  virtual Condition EmitComparisonCode(FlowGraphCompiler* compiler,
+                                       BranchLabels labels);
+
   virtual intptr_t DeoptimizationTarget() const {
     return GetDeoptId();
   }
 
   virtual Representation RequiredInputRepresentation(intptr_t idx) const {
     ASSERT((idx == 0) || (idx == 1));
     if (operation_cid() == kDoubleCid) return kUnboxedDouble;
     if (operation_cid() == kMintCid) return kUnboxedMint;
     return kTagged;
   }
@@ skipping 15 matching lines @@
                     Value* right,
                     intptr_t cid,
                     intptr_t deopt_id)
       : ComparisonInstr(token_pos, kind, left, right) {
     ASSERT(Token::IsRelationalOperator(kind));
     set_operation_cid(cid);
     deopt_id_ = deopt_id;  // Override generated deopt-id.
   }
 
   DECLARE_INSTRUCTION(RelationalOp)
+
+  virtual ComparisonInstr* CopyWithNewOperands(Value* left, Value* right);
+
   virtual CompileType ComputeType() const;
 
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
   virtual bool CanDeoptimize() const { return false; }
 
   virtual bool CanBecomeDeoptimizationTarget() const {
     // RelationalOp can be merged into Branch and thus needs an environment.
     return true;
   }
 
   virtual void EmitBranchCode(FlowGraphCompiler* compiler,
                               BranchInstr* branch);
 
+  virtual Condition EmitComparisonCode(FlowGraphCompiler* compiler,
+                                       BranchLabels labels);
 
   virtual intptr_t DeoptimizationTarget() const {
     return GetDeoptId();
   }
 
   virtual Representation RequiredInputRepresentation(intptr_t idx) const {
     ASSERT((idx == 0) || (idx == 1));
     if (operation_cid() == kDoubleCid) return kUnboxedDouble;
     if (operation_cid() == kMintCid) return kUnboxedMint;
     return kTagged;
   }
 
   virtual EffectSet Effects() const {
     return EffectSet::None();
   }
 
   virtual bool MayThrow() const { return false; }
 
  private:
   DISALLOW_COPY_AND_ASSIGN(RelationalOpInstr);
 };
 
 
 // TODO(vegorov): ComparisonInstr should be switched to use IfTheElseInstr for
 // materialization of true and false constants.
-class IfThenElseInstr : public TemplateDefinition<2> {
+class IfThenElseInstr : public Definition {
  public:
-  IfThenElseInstr(Token::Kind kind,
-                  Value* left,
-                  Value* right,
+  IfThenElseInstr(ComparisonInstr* comparison,
                   Value* if_true,
                   Value* if_false)
-      : kind_(kind),
+      : comparison_(comparison),
         if_true_(Smi::Cast(if_true->BoundConstant()).Value()),
         if_false_(Smi::Cast(if_false->BoundConstant()).Value()) {
-    ASSERT(Token::IsEqualityOperator(kind));
-    SetInputAt(0, left);
-    SetInputAt(1, right);
+    // Adjust uses at the comparison.
+    ASSERT(comparison->env() == NULL);
+    for (intptr_t i = comparison->InputCount() - 1; i >= 0; --i) {
+      comparison->InputAt(i)->set_instruction(this);
+    }
   }
 
   // Returns true if this combination of comparison and values flowing on
   // the true and false paths is supported on the current platform.
   static bool Supports(ComparisonInstr* comparison, Value* v1, Value* v2);
 
   DECLARE_INSTRUCTION(IfThenElse)
 
+  intptr_t InputCount() const { return comparison()->InputCount(); }
+
+  Value* InputAt(intptr_t i) const { return comparison()->InputAt(i); }
+
+  virtual bool CanDeoptimize() const {
+    return comparison()->CanDeoptimize();
+  }
+
+  virtual bool CanBecomeDeoptimizationTarget() const {
+    return comparison()->CanBecomeDeoptimizationTarget();
+  }
+
+  virtual LocationSummary* locs() {
+    if (comparison()->locs_ == NULL) {
+      LocationSummary* summary = MakeLocationSummary();
+      // The back-end expects the location summary to be stored in the
+      // comparison.
+      comparison()->locs_ = summary;
+    }
+    return comparison()->locs_;
+  }
+
+  virtual intptr_t DeoptimizationTarget() const {
+    return comparison()->DeoptimizationTarget();
+  }
+
+  virtual Representation RequiredInputRepresentation(intptr_t i) const {
+    return comparison()->RequiredInputRepresentation(i);
+  }
+
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
   virtual CompileType ComputeType() const;
 
   virtual void InferRange();
 
-  virtual bool CanDeoptimize() const { return false; }
-
-  Value* left() const { return inputs_[0]; }
-  Value* right() const { return inputs_[1]; }
+  ComparisonInstr* comparison() const { return comparison_; }
   intptr_t if_true() const { return if_true_; }
   intptr_t if_false() const { return if_false_; }
 
-  Token::Kind kind() const { return kind_; }
-
-  virtual bool AllowsCSE() const { return true; }
-  virtual EffectSet Effects() const { return EffectSet::None(); }
-  virtual EffectSet Dependencies() const { return EffectSet::None(); }
+  virtual bool AllowsCSE() const { return comparison()->AllowsCSE(); }
+  virtual EffectSet Effects() const { return comparison()->Effects(); }
+  virtual EffectSet Dependencies() const {
+    return comparison()->Dependencies();
+  }
   virtual bool AttributesEqual(Instruction* other) const {
     IfThenElseInstr* other_if_then_else = other->AsIfThenElse();
-    return (kind_ == other_if_then_else->kind_) &&
+    return comparison()->AttributesEqual(other_if_then_else->comparison()) &&
            (if_true_ == other_if_then_else->if_true_) &&
            (if_false_ == other_if_then_else->if_false_);
   }
 
-  virtual bool MayThrow() const { return false; }
+  virtual bool MayThrow() const { return comparison()->MayThrow(); }
 
  private:
-  const Token::Kind kind_;
+  virtual void RawSetInputAt(intptr_t i, Value* value) {
+    comparison()->RawSetInputAt(i, value);
+  }
+
+  ComparisonInstr* comparison_;
   const intptr_t if_true_;
   const intptr_t if_false_;
 
   DISALLOW_COPY_AND_ASSIGN(IfThenElseInstr);
 };
 
 
 class StaticCallInstr : public TemplateDefinition<0> {
  public:
   StaticCallInstr(intptr_t token_pos,
@@ skipping 3766 matching lines @@
   ForwardInstructionIterator* current_iterator_;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(FlowGraphVisitor);
 };
 
 
 }  // namespace dart
 
 #endif  // VM_INTERMEDIATE_LANGUAGE_H_