Abcd for performance check.

src/hydrogen-instructions.h

Index: src/hydrogen-instructions.h
diff --git a/src/hydrogen-instructions.h b/src/hydrogen-instructions.h
index d06e3184f817f2849d6e53395e3bff72aa061621..bc91d5b9f63d50cf1c6345488bb0005e284d39a2 100644
--- a/src/hydrogen-instructions.h
+++ b/src/hydrogen-instructions.h
@@ -629,6 +629,23 @@ class NumericRelation {
     return false;
   }
 
+  // The semantics of "ImpliedByEquality" is that if
+  // "rel.ImpliedByEquality(offset)" is true then
+  // "x == y" implies "(x + offset) rel y" .
+  bool ImpliedByEquality(int offset) {
+    switch (kind_) {
+      case NONE: return false;
+      case EQ: return (offset == 0);
+      case GT: return (offset >  0);
+      case GE: return (offset >= 0);
+      case LT: return (offset <  0);
+      case LE: return (offset <= 0);
+      case NE: return false;
+    }
+    UNREACHABLE();
+    return false;
+  }
+
   // The semantics of "IsExtendable" is that if
   // "rel.IsExtendable(direction)" is true then
   // "x rel y" implies "(x + direction) rel y" .
@@ -658,6 +675,47 @@ class NumericRelation {
         my_offset, my_scale, other_offset, other_scale);
   }
 
+  // CanBeChained returns true when
+  // "((x + offset) >> scale) rel limit" and "x other_relation y" imply
+  // "((y + offset) >> scale) rel limit".
+  // In other words, rel and other_relation go "in the same direction"
+  // and therefore can be "chained".
+  bool CanBeChained(NumericRelation other_relation) {
+    switch (kind_) {
+      case NONE: return false;
+      case EQ: return (other_relation.kind_ == EQ);
+      case GT:
+      case GE:
+        return (other_relation.kind_ == GT) || (other_relation.kind_ == GE);
+      case LT:
+      case LE:
+        return (other_relation.kind_ == LT) || (other_relation.kind_ == LE);
+      case NE: return false;
+    }
+    UNREACHABLE();
+    return false;
+  }
+
+  bool ApplyToValues(int32_t value, int32_t other_value) {
+    switch (kind_) {
+      case NONE: return false;
+      case EQ: return value == other_value;
+      case GT: return value >  other_value;
+      case GE: return value >= other_value;
+      case LT: return value <  other_value;
+      case LE: return value <= other_value;
+      case NE: return value != other_value;
+    }
+    UNREACHABLE();
+    return false;
+  }
+
+  int Compare(NumericRelation other) {
+    int my_value = static_cast<int>(kind_);
+    int other_value = static_cast<int>(other.kind_);
+    return my_value - other_value;
+  }
+
  private:
   // ComponentsImply returns true when
   // "((x + my_offset) >> my_scale) rel y" implies
@@ -732,8 +790,11 @@ class DecompositionResult BASE_EMBEDDED {
 
 class RangeEvaluationContext BASE_EMBEDDED {
  public:
-  RangeEvaluationContext(HValue* value, HValue* upper);
+  RangeEvaluationContext(HValue* value,
+                         HValue* upper,
+                         HBasicBlock* starting_block);
 
+  HBasicBlock* starting_block() { return starting_block_; }
   HValue* lower_bound() { return lower_bound_; }
   HValue* lower_bound_guarantee() { return lower_bound_guarantee_; }
   HValue* candidate() { return candidate_; }
@@ -760,6 +821,7 @@ class RangeEvaluationContext BASE_EMBEDDED {
  private:
   HValue* ConvertGuarantee(HValue* guarantee);
 
+  HBasicBlock* starting_block_;
   HValue* lower_bound_;
   HValue* lower_bound_guarantee_;
   HValue* candidate_;
@@ -770,6 +832,101 @@ class RangeEvaluationContext BASE_EMBEDDED {
 };
 
 
+class NumericRelationTableElement {
+ public:
+  int value_id() const { return value_id_; }
+  NumericRelation relation() const { return relation_; }
+  int other_value_id() const { return other_value_id_; }
+  int offset() const { return offset_; }
+  int scale() const { return scale_; }
+  int block_id() const { return block_id_; }
+  bool result() const { return result_; }
+
+  NumericRelationTableElement(int value_id,
+                              NumericRelation relation,
+                              int other_value_id,
+                              int offset,
+                              int scale,
+                              int block_id,
+                              bool result)
+      : value_id_(value_id),
+        relation_(relation),
+        other_value_id_(other_value_id),
+        offset_(offset),
+        scale_(scale),
+        block_id_(block_id),
+        result_(result) {}
+
+  NumericRelationTableElement(const NumericRelationTableElement& other)
+      : value_id_(other.value_id()),
+        relation_(other.relation()),
+        other_value_id_(other.other_value_id()),
+        offset_(other.offset()),
+        scale_(other.scale()),
+        block_id_(other.block_id()),
+        result_(other.result()) {}
+
+  int Compare(const NumericRelationTableElement& other) const {
+    int result = Comparator(value_id(), other.value_id());
+    if (result != 0) return result;
+    result = relation().Compare(other.relation());
+    if (result != 0) return result;
+    result = Comparator(other_value_id(), other.other_value_id());
+    if (result != 0) return result;
+    result = Comparator(offset(), other.offset());
+    if (result != 0) return result;
+    result = Comparator(block_id(), other.block_id());
+    if (result != 0) return result;
+    return Comparator(scale(), other.scale());
+  }
+
+ private:
+  static int Comparator(int value, int other_value) {
+    return value - other_value;
+  }
+
+  int value_id_;
+  NumericRelation relation_;
+  int other_value_id_;
+  int offset_;
+  int scale_;
+  int block_id_;
+  bool result_;
+};
+
+
+class NumericRelationTable {
+ public:
+  bool IsInTable(int value_id,
+                 NumericRelation relation,
+                 int other_value_id,
+                 int offset,
+                 int scale,
+                 int block_id,
+                 bool* result);
+
+  void AddToTable(int value_id,
+                  NumericRelation relation,
+                  int other_value_id,
+                  int offset,
+                  int scale,
+                  int block_id,
+                  bool result);
+
+  void Clear();
+
+  explicit NumericRelationTable(Zone* zone) : table_(8, zone), zone_(zone) {}
+
+ private:
+  int FindInsertionPoint(const NumericRelationTableElement& element,
+                         bool* result);
+  void Insert(const NumericRelationTableElement& element, int index);
+
+  ZoneList<NumericRelationTableElement> table_;
+  Zone* zone_;
+};
+
+
 typedef EnumSet<GVNFlag> GVNFlagSet;
 
 
@@ -1088,7 +1245,8 @@ class HValue: public ZoneObject {
                       int offset = 0,
                       int scale = 0);
 
-  bool TryGuaranteeRange(HValue* upper_bound);
+  bool TryGuaranteeRange(HValue* upper_bound,
+                         HBasicBlock* starting_block_for_hoisting = NULL);
   virtual bool TryDecompose(DecompositionResult* decomposition) {
     if (RedefinedOperand() != NULL) {
       return RedefinedOperand()->TryDecompose(decomposition);
@@ -1098,6 +1256,10 @@ class HValue: public ZoneObject {
   }
 
  protected:
+  bool EvaluateRelationRecursively(NumericRelation relation,
+                                   HValue* other,
+                                   int offset = 0,
+                                   int scale = 0);
   void TryGuaranteeRangeRecursive(RangeEvaluationContext* context);
 
   enum RangeGuaranteeDirection {
@@ -1407,14 +1569,17 @@ class HDummyUse: public HTemplateInstruction<1> {
 
 class HNumericConstraint : public HTemplateInstruction<2> {
  public:
-  static HNumericConstraint* AddToGraph(HValue* constrained_value,
-                                        NumericRelation relation,
-                                        HValue* related_value,
-                                        HInstruction* insertion_point = NULL);
+  static HNumericConstraint* AddToGraph(
+      HValue* constrained_value,
+      NumericRelation relation,
+      HValue* related_value,
+      HInstruction* insertion_point = NULL,
+      HBasicBlock* jump_target_when_false = NULL);
 
   HValue* constrained_value() { return OperandAt(0); }
   HValue* related_value() { return OperandAt(1); }
   NumericRelation relation() { return relation_; }
+  HBasicBlock* jump_target_when_false() { return jump_target_when_false_; }
 
   virtual int RedefinedOperandIndex() { return 0; }
   virtual bool IsPurelyInformativeDefinition() { return true; }
@@ -1432,7 +1597,12 @@ class HNumericConstraint : public HTemplateInstruction<2> {
     if (related_value() == other_related_value) {
       return relation().CompoundImplies(other_relation, offset, scale);
     } else {
-      return false;
+      if (relation().CanBeChained(other_relation)) {
+        return related_value()->IsRelationTrue(
+            other_relation, other_related_value, offset, scale);
+      } else {
+        return false;
+      }
     }
   }
 
@@ -1441,13 +1611,15 @@ class HNumericConstraint : public HTemplateInstruction<2> {
  private:
   HNumericConstraint(HValue* constrained_value,
                      NumericRelation relation,
-                     HValue* related_value)
-      : relation_(relation) {
+                     HValue* related_value,
+                     HBasicBlock* jump_target_when_false)
+      : relation_(relation), jump_target_when_false_(jump_target_when_false) {
     SetOperandAt(0, constrained_value);
     SetOperandAt(1, related_value);
   }
 
   NumericRelation relation_;
+  HBasicBlock* jump_target_when_false_;
 };
 
 
@@ -3099,6 +3271,9 @@ class HPhi: public HValue {
 };
 
 
+class HBoundsCheck;
+
+
 class HInductionVariableAnnotation : public HUnaryOperation {
  public:
   static HInductionVariableAnnotation* AddToGraph(HPhi* phi,
@@ -3114,6 +3289,7 @@ class HInductionVariableAnnotation : public HUnaryOperation {
     return representation();
   }
 
+  virtual void TryGuaranteeRangeChanging(RangeEvaluationContext* context);
   virtual void PrintDataTo(StringStream* stream);
 
   virtual bool IsRelationTrueInternal(NumericRelation other_relation,
@@ -3123,19 +3299,27 @@ class HInductionVariableAnnotation : public HUnaryOperation {
     if (induction_base() == other_related_value) {
       return relation().CompoundImplies(other_relation, offset, scale);
     } else {
-      return false;
+      if (relation().CanBeChained(other_relation)) {
+        return induction_base()->IsRelationTrue(
+            other_relation, other_related_value, offset, scale);
+      } else {
+        return false;
+      }
     }
   }
 
+  const ZoneList<HBoundsCheck*>* hoisted_checks() const {
+    return &hoisted_checks_;
+  }
+  void AddHoistedCheck(HBoundsCheck* check);
+
   DECLARE_CONCRETE_INSTRUCTION(InductionVariableAnnotation)
 
  private:
   HInductionVariableAnnotation(HPhi* phi,
                                NumericRelation relation,
-                               int operand_index)
-      : HUnaryOperation(phi),
-    phi_(phi), relation_(relation), operand_index_(operand_index) {
-  }
+                               int operand_index,
+                               Zone* zone);
 
   // We need to store the phi both here and in the instruction operand because
   // the operand can change if a new idef of the phi is added between the phi
@@ -3143,6 +3327,7 @@ class HInductionVariableAnnotation : public HUnaryOperation {
   HPhi* phi_;
   NumericRelation relation_;
   int operand_index_;
+  ZoneList<HBoundsCheck*> hoisted_checks_;
 };
 
 
@@ -3288,6 +3473,20 @@ class HConstant: public HTemplateInstruction<0> {
 
   bool BooleanValue() const { return boolean_value_; }
 
+  virtual bool IsRelationTrueInternal(NumericRelation relation,
+                                      HValue* related_value,
+                                      int offset = 0,
+                                      int scale = 0) {
+    if (HasInteger32Value() &&
+        related_value->IsInteger32Constant()) {
+      int32_t value = (Integer32Value() + offset) >> scale;
+      int32_t other_value = related_value->GetInteger32Constant();
+      return relation.ApplyToValues(value, other_value);
+    } else {
+      return false;
+    }
+  }
+
   virtual intptr_t Hashcode() {
     if (has_int32_value_) {
       return static_cast<intptr_t>(int32_value_);
@@ -3582,7 +3781,8 @@ class HBoundsCheck: public HTemplateInstruction<2> {
                Representation r = Representation::None())
     : key_mode_(key_mode), skip_check_(false),
       base_(NULL), offset_(0), scale_(0),
-      responsibility_direction_(DIRECTION_NONE) {
+      responsibility_direction_(DIRECTION_NONE),
+      allow_equality_(false) {
     SetOperandAt(0, index);
     SetOperandAt(1, length);
     if (r.IsNone()) {
@@ -3597,8 +3797,11 @@ class HBoundsCheck: public HTemplateInstruction<2> {
     SetFlag(kUseGVN);
   }
 
-  bool skip_check() { return skip_check_; }
-  void set_skip_check(bool skip_check) { skip_check_ = skip_check; }
+  bool skip_check() const { return skip_check_; }
+  void set_skip_check() {
+    isolate()->counters()->bounds_checks_removed()->Increment();
+    skip_check_ = true;
+  }
   HValue* base() { return base_; }
   int offset() { return offset_; }
   int scale() { return scale_; }
@@ -3633,6 +3836,9 @@ class HBoundsCheck: public HTemplateInstruction<2> {
   virtual Representation observed_input_representation(int index) {
     return Representation::Integer32();
   }
+  virtual bool IsDeletable() const {
+    return skip_check();
+  }
 
   virtual bool IsRelationTrueInternal(NumericRelation relation,
                                       HValue* related_value,
@@ -3644,6 +3850,8 @@ class HBoundsCheck: public HTemplateInstruction<2> {
 
   HValue* index() { return OperandAt(0); }
   HValue* length() { return OperandAt(1); }
+  bool allow_equality() { return allow_equality_; }
+  void set_allow_equality(bool v) { allow_equality_ = v; }
 
   virtual int RedefinedOperandIndex() { return 0; }
   virtual bool IsPurelyInformativeDefinition() { return skip_check(); }
@@ -3667,6 +3875,7 @@ class HBoundsCheck: public HTemplateInstruction<2> {
   int offset_;
   int scale_;
   RangeGuaranteeDirection responsibility_direction_;
+  bool allow_equality_;
 };
 
 
@@ -3683,7 +3892,10 @@ class HBoundsCheckBaseIndexInformation: public HTemplateInstruction<2> {
   }
 
   HValue* base_index() { return OperandAt(0); }
-  HBoundsCheck* bounds_check() { return HBoundsCheck::cast(OperandAt(1)); }
+  HBoundsCheck* bounds_check() {
+    return OperandAt(1)->IsBoundsCheck()
+        ? HBoundsCheck::cast(OperandAt(1)) : NULL;
+  }
 
   DECLARE_CONCRETE_INSTRUCTION(BoundsCheckBaseIndexInformation)
 
@@ -4292,6 +4504,11 @@ class HAdd: public HArithmeticBinaryOperation {
     }
   }
 
+  virtual bool IsRelationTrueInternal(NumericRelation relation,
+                                      HValue* other,
+                                      int offset = 0,
+                                      int scale = 0);
+
   DECLARE_CONCRETE_INSTRUCTION(Add)
 
  protected:
@@ -4554,6 +4771,20 @@ class HShl: public HBitwiseBinaryOperation {
                            HValue* left,
                            HValue* right);
 
+  virtual bool TryDecompose(DecompositionResult* decomposition) {
+    if (right()->IsInteger32Constant() &&
+        right()->GetInteger32Constant() <= 1 &&
+        right()->GetInteger32Constant() >= 0) {
+      if (decomposition->Apply(left(), 0, - right()->GetInteger32Constant())) {
+        // This is intended to look for HAdd and HSub, to handle compounds
+        // like ((base + offset) << scale) with one single decomposition.
+        left()->TryDecompose(decomposition);
+        return true;
+      }
+    }
+    return false;
+  }
+
   virtual Range* InferRange(Zone* zone);
 
   DECLARE_CONCRETE_INSTRUCTION(Shl)
@@ -4575,7 +4806,8 @@ class HShr: public HBitwiseBinaryOperation {
                            HValue* right);
 
   virtual bool TryDecompose(DecompositionResult* decomposition) {
-    if (right()->IsInteger32Constant()) {
+    if (right()->IsInteger32Constant() &&
+        right()->GetInteger32Constant() >= 0) {
       if (decomposition->Apply(left(), 0, right()->GetInteger32Constant())) {
         // This is intended to look for HAdd and HSub, to handle compounds
         // like ((base + offset) >> scale) with one single decomposition.
@@ -4607,7 +4839,8 @@ class HSar: public HBitwiseBinaryOperation {
                            HValue* right);
 
   virtual bool TryDecompose(DecompositionResult* decomposition) {
-    if (right()->IsInteger32Constant()) {
+    if (right()->IsInteger32Constant() &&
+        right()->GetInteger32Constant() >= 0) {
       if (decomposition->Apply(left(), 0, right()->GetInteger32Constant())) {
         // This is intended to look for HAdd and HSub, to handle compounds
         // like ((base + offset) >> scale) with one single decomposition.