Abcd for performance check.

src/hydrogen-instructions.h

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 611 matching lines @@
           || (other_relation.kind_ == LE)
           || (other_relation.kind_ == NE);
       case GE: return (other_relation.kind_ == GE);
       case LE: return (other_relation.kind_ == LE);
       case NE: return (other_relation.kind_ == NE);
     }
     UNREACHABLE();
     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" .
   bool IsExtendable(int direction) {
     switch (kind_) {
       case NONE: return false;
       case EQ: return false;
       case GT: return (direction >= 0);
       case GE: return (direction >= 0);
       case LT: return (direction <= 0);
       case LE: return (direction <= 0);
       case NE: return false;
     }
     UNREACHABLE();
     return false;
   }
 
   // CompoundImplies returns true when
   // "((x + my_offset) >> my_scale) rel y" implies
   // "((x + other_offset) >> other_scale) other_relation y".
   bool CompoundImplies(NumericRelation other_relation,
                        int my_offset,
                        int my_scale,
                        int other_offset = 0,
                        int other_scale = 0) {
     return Implies(other_relation) && ComponentsImply(
         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
   // "((x + other_offset) >> other_scale) rel y".
   bool ComponentsImply(int my_offset,
                        int my_scale,
                        int other_offset,
                        int other_scale) {
     switch (kind_) {
       case NONE: break;  // Fall through to UNREACHABLE().
@@ skipping 54 matching lines @@
   }
 
   HValue* base_;
   int offset_;
   int scale_;
 };
 
 
 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_; }
   HValue* upper_bound() { return upper_bound_; }
   HValue* upper_bound_guarantee() { return upper_bound_guarantee_; }
   int offset() { return offset_; }
   int scale() { return scale_; }
 
   bool is_range_satisfied() {
     return lower_bound_guarantee() != NULL && upper_bound_guarantee() != NULL;
   }
 
   void set_lower_bound_guarantee(HValue* guarantee) {
     lower_bound_guarantee_ = ConvertGuarantee(guarantee);
   }
   void set_upper_bound_guarantee(HValue* guarantee) {
     upper_bound_guarantee_ = ConvertGuarantee(guarantee);
   }
 
   void swap_candidate(DecompositionResult* other_candicate) {
     other_candicate->SwapValues(&candidate_, &offset_, &scale_);
   }
 
  private:
   HValue* ConvertGuarantee(HValue* guarantee);
 
+  HBasicBlock* starting_block_;
   HValue* lower_bound_;
   HValue* lower_bound_guarantee_;
   HValue* candidate_;
   HValue* upper_bound_;
   HValue* upper_bound_guarantee_;
   int offset_;
   int scale_;
 };
 
 
+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;
 
 
 class HValue: public ZoneObject {
  public:
   static const int kNoNumber = -1;
 
   enum Flag {
     kFlexibleRepresentation,
     // Participate in Global Value Numbering, i.e. elimination of
@@ skipping 298 matching lines @@
 
 #ifdef DEBUG
   virtual void Verify() = 0;
 #endif
 
   bool IsRelationTrue(NumericRelation relation,
                       HValue* other,
                       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);
     } else {
       return false;
     }
   }
 
  protected:
+  bool EvaluateRelationRecursively(NumericRelation relation,
+                                   HValue* other,
+                                   int offset = 0,
+                                   int scale = 0);
   void TryGuaranteeRangeRecursive(RangeEvaluationContext* context);
 
   enum RangeGuaranteeDirection {
     DIRECTION_NONE = 0,
     DIRECTION_UPPER = 1,
     DIRECTION_LOWER = 2,
     DIRECTION_BOTH = DIRECTION_UPPER | DIRECTION_LOWER
   };
   virtual void SetResponsibilityForRange(RangeGuaranteeDirection direction) {}
   virtual void TryGuaranteeRangeChanging(RangeEvaluationContext* context) {}
@@ skipping 289 matching lines @@
   }
 
   virtual void PrintDataTo(StringStream* stream);
 
   DECLARE_CONCRETE_INSTRUCTION(DummyUse);
 };
 
 
 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; }
 
   virtual Representation RequiredInputRepresentation(int index) {
     return representation();
   }
 
   virtual void PrintDataTo(StringStream* stream);
 
   virtual bool IsRelationTrueInternal(NumericRelation other_relation,
                                       HValue* other_related_value,
                                       int offset = 0,
                                       int scale = 0) {
     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;
+      }
     }
   }
 
   DECLARE_CONCRETE_INSTRUCTION(NumericConstraint)
 
  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_;
 };
 
 
 // We insert soft-deoptimize when we hit code with unknown typefeedback,
 // so that we get a chance of re-optimizing with useful typefeedback.
 // HSoftDeoptimize does not end a basic block as opposed to HDeoptimize.
 class HSoftDeoptimize: public HTemplateInstruction<0> {
  public:
   virtual Representation RequiredInputRepresentation(int index) {
     return Representation::None();
@@ skipping 1631 matching lines @@
   ZoneList<HValue*> inputs_;
   int merged_index_;
 
   int non_phi_uses_[Representation::kNumRepresentations];
   int indirect_uses_[Representation::kNumRepresentations];
   int phi_id_;
   bool is_convertible_to_integer_;
 };
 
 
+class HBoundsCheck;
+
+
 class HInductionVariableAnnotation : public HUnaryOperation {
  public:
   static HInductionVariableAnnotation* AddToGraph(HPhi* phi,
                                                   NumericRelation relation,
                                                   int operand_index);
 
   NumericRelation relation() { return relation_; }
   HValue* induction_base() { return phi_->OperandAt(operand_index_); }
 
   virtual int RedefinedOperandIndex() { return 0; }
   virtual bool IsPurelyInformativeDefinition() { return true; }
   virtual Representation RequiredInputRepresentation(int index) {
     return representation();
   }
 
+  virtual void TryGuaranteeRangeChanging(RangeEvaluationContext* context);
   virtual void PrintDataTo(StringStream* stream);
 
   virtual bool IsRelationTrueInternal(NumericRelation other_relation,
                                       HValue* other_related_value,
                                       int offset = 0,
                                       int scale = 0) {
     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
   // and this instruction (inserting an idef updates every use).
   HPhi* phi_;
   NumericRelation relation_;
   int operand_index_;
+  ZoneList<HBoundsCheck*> hoisted_checks_;
 };
 
 
 class HArgumentsObject: public HTemplateInstruction<0> {
  public:
   HArgumentsObject() {
     set_representation(Representation::Tagged());
     SetFlag(kIsArguments);
   }
 
@@ skipping 125 matching lines @@
   Handle<String> StringValue() const {
     ASSERT(HasStringValue());
     return Handle<String>::cast(handle_);
   }
   bool HasInternalizedStringValue() const {
     return HasStringValue() && is_internalized_string_;
   }
 
   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_);
     } else if (has_double_value_) {
       return static_cast<intptr_t>(BitCast<int64_t>(double_value_));
     } else {
       ASSERT(!handle_.is_null());
       return unique_id_.Hashcode();
     }
   }
@@ skipping 274 matching lines @@
   // HGraphBuilder::AddBoundsCheck() helper, which also guards the index with
   // a HCheckSmiOrInt32 check.
   // However when building stubs, where we know that the arguments are Int32,
   // it makes sense to invoke this constructor directly.
   HBoundsCheck(HValue* index,
                HValue* length,
                BoundsCheckKeyMode key_mode = DONT_ALLOW_SMI_KEY,
                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()) {
       // In the normal compilation pipeline the representation is flexible
       // (see InferRepresentation).
       SetFlag(kFlexibleRepresentation);
     } else {
       // When compiling stubs we want to set the representation explicitly
       // so the compilation pipeline can skip the HInferRepresentation phase.
       set_representation(r);
     }
     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_; }
   bool index_can_increase() {
     return (responsibility_direction_ & DIRECTION_LOWER) == 0;
   }
   bool index_can_decrease() {
     return (responsibility_direction_ & DIRECTION_UPPER) == 0;
   }
 
@@ skipping 14 matching lines @@
       return false;
     }
   }
 
   virtual Representation RequiredInputRepresentation(int arg_index) {
     return representation();
   }
   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,
                                       int offset = 0,
                                       int scale = 0);
 
   virtual void PrintDataTo(StringStream* stream);
   virtual void InferRepresentation(HInferRepresentation* h_infer);
 
   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(); }
   virtual void AddInformativeDefinitions();
 
   DECLARE_CONCRETE_INSTRUCTION(BoundsCheck)
 
  protected:
   friend class HBoundsCheckBaseIndexInformation;
 
   virtual void SetResponsibilityForRange(RangeGuaranteeDirection direction) {
     responsibility_direction_ = static_cast<RangeGuaranteeDirection>(
         responsibility_direction_ | direction);
   }
 
   virtual bool DataEquals(HValue* other) { return true; }
   virtual void TryGuaranteeRangeChanging(RangeEvaluationContext* context);
   BoundsCheckKeyMode key_mode_;
   bool skip_check_;
   HValue* base_;
   int offset_;
   int scale_;
   RangeGuaranteeDirection responsibility_direction_;
+  bool allow_equality_;
 };
 
 
 class HBoundsCheckBaseIndexInformation: public HTemplateInstruction<2> {
  public:
   explicit HBoundsCheckBaseIndexInformation(HBoundsCheck* check) {
     DecompositionResult decomposition;
     if (check->index()->TryDecompose(&decomposition)) {
       SetOperandAt(0, decomposition.base());
       SetOperandAt(1, check);
     } else {
       UNREACHABLE();
     }
   }
 
   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)
 
   virtual Representation RequiredInputRepresentation(int arg_index) {
     return representation();
   }
 
   virtual bool IsRelationTrueInternal(NumericRelation relation,
                                       HValue* related_value,
                                       int offset = 0,
@@ skipping 588 matching lines @@
       decomposition->Apply(right(), left()->GetInteger32Constant());
       return true;
     } else if (right()->IsInteger32Constant()) {
       decomposition->Apply(left(), right()->GetInteger32Constant());
       return true;
     } else {
       return false;
     }
   }
 
+  virtual bool IsRelationTrueInternal(NumericRelation relation,
+                                      HValue* other,
+                                      int offset = 0,
+                                      int scale = 0);
+
   DECLARE_CONCRETE_INSTRUCTION(Add)
 
  protected:
   virtual bool DataEquals(HValue* other) { return true; }
 
   virtual Range* InferRange(Zone* zone);
 
  private:
   HAdd(HValue* context, HValue* left, HValue* right)
       : HArithmeticBinaryOperation(context, left, right) {
@@ skipping 242 matching lines @@
 };
 
 
 class HShl: public HBitwiseBinaryOperation {
  public:
   static HInstruction* New(Zone* zone,
                            HValue* context,
                            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)
 
  protected:
   virtual bool DataEquals(HValue* other) { return true; }
 
  private:
   HShl(HValue* context, HValue* left, HValue* right)
       : HBitwiseBinaryOperation(context, left, right) { }
 };
 
 
 class HShr: public HBitwiseBinaryOperation {
  public:
   static HInstruction* New(Zone* zone,
                            HValue* context,
                            HValue* left,
                            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.
         left()->TryDecompose(decomposition);
         return true;
       }
     }
     return false;
   }
 
@@ skipping 11 matching lines @@
 
 
 class HSar: public HBitwiseBinaryOperation {
  public:
   static HInstruction* New(Zone* zone,
                            HValue* context,
                            HValue* left,
                            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.
         left()->TryDecompose(decomposition);
         return true;
       }
     }
     return false;
   }
 
@@ skipping 1840 matching lines @@
   virtual bool IsDeletable() const { return true; }
 };
 
 
 #undef DECLARE_INSTRUCTION
 #undef DECLARE_CONCRETE_INSTRUCTION
 
 } }  // namespace v8::internal
 
 #endif  // V8_HYDROGEN_INSTRUCTIONS_H_