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 660 matching lines @@
   // "((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;
+  }
+
  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_;
 };
 
 
@@ skipping 300 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:
   void TryGuaranteeRangeRecursive(RangeEvaluationContext* context);
@@ skipping 301 matching lines @@
 
   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);
+                                        HInstruction* insertion_point = NULL,
+                                        HBasicBlock* other_block = NULL);

[Jakob Kummerow, 2013/04/17 11:34:15]

I think "other_block" either needs a comment or a more descriptive name.
"jump_target_when_false"?

[Massi, 2013/05/07 11:32:03]

Done.

 
   HValue* constrained_value() { return OperandAt(0); }
   HValue* related_value() { return OperandAt(1); }
   NumericRelation relation() { return relation_; }
+  HBasicBlock* other_block() { return other_block_; }
 
   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* other_block)
+    : relation_(relation), other_block_(other_block) {

[Jakob Kummerow, 2013/04/17 11:34:15]

nit: indentation

[Massi, 2013/05/07 11:32:03]

Done.

     SetOperandAt(0, constrained_value);
     SetOperandAt(1, related_value);
   }
 
   NumericRelation relation_;
+  HBasicBlock* other_block_;
 };
 
 
 // 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 1621 matching lines @@
   int merged_index_;
 
   int non_phi_uses_[Representation::kNumRepresentations];
   int indirect_uses_[Representation::kNumRepresentations];
   int phi_id_;
   bool is_live_;
   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 127 matching lines @@
   bool HasInternalizedStringValue() const {
     return HasStringValue() && is_internalized_string_;
   }
 
   bool BooleanValue() const { return boolean_value_; }
 
   bool IsUint32() {
     return HasInteger32Value() && (Integer32Value() >= 0);
   }
 
+  virtual bool IsRelationTrueInternal(NumericRelation relation,
+                                      HValue* related_value,
+                                      int offset = 0,
+                                      int scale = 0) {
+    if (HasInteger32Value()
+        && related_value->IsInteger32Constant()) {

[Jakob Kummerow, 2013/04/17 11:34:15]

nit: we're pretty consistent about putting binary operators at the end of the
first line.

[Massi, 2013/05/07 11:32:03]

Done.

+      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;
 
     if (has_int32_value_) {
       hash = static_cast<intptr_t>(int32_value_);
     } else if (has_double_value_) {
       hash = static_cast<intptr_t>(BitCast<int64_t>(double_value_));
     } else {
       ASSERT(!handle_.is_null());
@@ skipping 263 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);
@@ skipping 41 matching lines @@
   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 607 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 224 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) {

[Jakob Kummerow, 2013/04/17 11:34:15]

As discussed, I think you need an additional check here that
right()->GetInteger32Constant >= 0.

Please check right shifts for the same issue.

And a nit: '&&' on the previous line please.

[Massi, 2013/05/07 11:32:03]

Done.

+      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.

[Jakob Kummerow, 2013/04/17 11:34:15]

s/>>/<</ ?

[Massi, 2013/05/07 11:32:03]

Done.

+        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) { }
@@ skipping 1871 matching lines @@
   virtual bool IsDeletable() const { return true; }
 };
 
 
 #undef DECLARE_INSTRUCTION
 #undef DECLARE_CONCRETE_INSTRUCTION
 
 } }  // namespace v8::internal
 
 #endif  // V8_HYDROGEN_INSTRUCTIONS_H_