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 7acec8bcd5ebc3e2e0757d312ee591f5e5174e72..b99437e13f8c09e74aa154811af88e5290623a5b 100644
--- a/src/hydrogen-instructions.h
+++ b/src/hydrogen-instructions.h
@@ -649,6 +649,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" .
@@ -678,6 +695,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
@@ -752,8 +810,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_; }
@@ -780,6 +841,7 @@ class RangeEvaluationContext BASE_EMBEDDED {
  private:
   HValue* ConvertGuarantee(HValue* guarantee);
 
+  HBasicBlock* starting_block_;
   HValue* lower_bound_;
   HValue* lower_bound_guarantee_;
   HValue* candidate_;
@@ -790,6 +852,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) :

[Jakob Kummerow, 2013/05/15 12:56:35]

nit: colon goes on the next line, with 4 spaces of indentation relative to
"NumericRelationTableElement(".

[Massi, 2013/05/21 12:49:56]

Done.

+    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) :

[Jakob Kummerow, 2013/05/15 12:56:35]

nit: same here

[Massi, 2013/05/21 12:49:56]

Done.

+    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;
 
 
@@ -1100,7 +1257,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);
@@ -1110,6 +1268,10 @@ class HValue: public ZoneObject {
   }
 
  protected:
+  bool EvaluateRelationRecursively(NumericRelation relation,
+                                   HValue* other,
+                                   int offset = 0,
+                                   int scale = 0);
   void TryGuaranteeRangeRecursive(RangeEvaluationContext* context);
 
   enum RangeGuaranteeDirection {
@@ -1419,14 +1581,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; }
@@ -1444,7 +1609,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;
+      }
     }
   }
 
@@ -1453,13 +1623,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_;
 };
 
 
@@ -3101,6 +3273,9 @@ class HPhi: public HValue {
 };
 
 
+class HBoundsCheck;
+
+
 class HInductionVariableAnnotation : public HUnaryOperation {
  public:
   static HInductionVariableAnnotation* AddToGraph(HPhi* phi,
@@ -3116,6 +3291,7 @@ class HInductionVariableAnnotation : public HUnaryOperation {
     return representation();
   }
 
+  virtual void TryGuaranteeRangeChanging(RangeEvaluationContext* context);
   virtual void PrintDataTo(StringStream* stream);
 
   virtual bool IsRelationTrueInternal(NumericRelation other_relation,
@@ -3125,19 +3301,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
@@ -3145,6 +3329,7 @@ class HInductionVariableAnnotation : public HUnaryOperation {
   HPhi* phi_;
   NumericRelation relation_;
   int operand_index_;
+  ZoneList<HBoundsCheck*> hoisted_checks_;
 };
 
 
@@ -3292,6 +3477,20 @@ class HConstant: public HTemplateInstruction<0> {
     return HasInteger32Value() && (Integer32Value() >= 0);
   }
 
+  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() {
     ASSERT_ALLOCATION_DISABLED;
     intptr_t hash;
@@ -3575,7 +3774,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()) {
@@ -3590,8 +3790,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_; }
@@ -3626,6 +3829,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,
@@ -3637,6 +3843,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(); }
@@ -3660,6 +3868,7 @@ class HBoundsCheck: public HTemplateInstruction<2> {
   int offset_;
   int scale_;
   RangeGuaranteeDirection responsibility_direction_;
+  bool allow_equality_;
 };
 
 
@@ -3676,7 +3885,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)
 
@@ -4304,6 +4516,11 @@ class HAdd: public HArithmeticBinaryOperation {
     }
   }
 
+  virtual bool IsRelationTrueInternal(NumericRelation relation,
+                                      HValue* other,
+                                      int offset = 0,
+                                      int scale = 0);
+
   DECLARE_CONCRETE_INSTRUCTION(Add)
 
  protected:
@@ -4548,6 +4765,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)
@@ -4569,7 +4800,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.
@@ -4601,7 +4833,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.