Handling expression decomposition and array bounds check hoisting: working code with lots of debugg…

src/hydrogen-instructions.h

Index: src/hydrogen-instructions.h
diff --git a/src/hydrogen-instructions.h b/src/hydrogen-instructions.h
index 2d763d55f0df2eaf0a779ccf7fc1da5898b9bd2d..15cfb88212137cb25375f2a0c760c4bb56500608 100644
--- a/src/hydrogen-instructions.h
+++ b/src/hydrogen-instructions.h
@@ -75,6 +75,7 @@ class LChunkBuilder;
   V(BitNot)                                    \
   V(BlockEntry)                                \
   V(BoundsCheck)                               \
+  V(BoundsCheckBaseIndexInformation)           \
   V(Branch)                                    \
   V(CallConstantFunction)                      \
   V(CallFunction)                              \
@@ -666,13 +667,97 @@ class NumericRelation {
     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);
+  }
+
  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: return false;

[Jakob Kummerow, 2013/03/14 12:50:09]

As an additional safeguard, I'd prefer:
case NONE: break;  // Fall through to UNREACHABLE().

[Massi, 2013/03/14 15:07:18]

Done.

+      case EQ:
+      case NE: return my_offset == other_offset && my_scale == other_scale;
+      case GT:
+      case GE: return my_offset <= other_offset && my_scale >= other_scale;
+      case LT:
+      case LE: return my_offset >= other_offset && my_scale <= other_scale;
+    }
+    UNREACHABLE();
+    return false;
+  }
+
   explicit NumericRelation(Kind kind) : kind_(kind) {}
 
   Kind kind_;
 };
 
 
+class RangeEvaluationContext BASE_EMBEDDED {
+ public:
+  RangeEvaluationContext(HValue* value, HValue* upper);
+
+  HValue* lower_bound() { return lower_bound_; }
+  HValue* lower_check_guarantee() { return lower_check_guarantee_; }
+  HValue* candidate() { return candidate_; }
+  HValue* upper_bound() { return upper_bound_; }
+  HValue* upper_check_guarantee() { return upper_check_guarantee_; }
+  int offset() { return offset_; }
+  int scale() { return scale_; }
+
+  bool is_lower_bound_satisfied() { return lower_check_guarantee_ != NULL; }

[Jakob Kummerow, 2013/03/14 12:50:09]

I'm still not quite happy with these names.
(1) What's a "check guarantee"? I think it would make more sense to call it
either "lower_check_" or "lower_bound_guarantee_".
(2) This method right here is very similar to a getter. Its name should match
the variable that's being looked at:
bool has_foo() { return foo_ != NULL; }
(I still think it would be fine to just inline the NULL checks, but if you
prefer explicit methods that's OK too.)

[Massi, 2013/03/14 15:07:18]

Done.

+  bool is_upper_bound_satisfied() { return upper_check_guarantee_ != NULL; }
+  bool is_range_satisfied() {
+    return is_lower_bound_satisfied() && is_upper_bound_satisfied();
+  }
+
+  void set_lower_check_guarantee(HValue* guarantee) {
+    lower_check_guarantee_ = ConvertGuarantee(guarantee);
+  }
+  void set_upper_check_guarantee(HValue* guarantee) {
+    upper_check_guarantee_ = ConvertGuarantee(guarantee);
+  }
+
+  void swap_candidate(HValue** other_candidate,
+                      int* other_offset,
+                      int* other_scale) {
+    swap(&candidate_, other_candidate);
+    swap(&offset_, other_offset);
+    swap(&scale_, other_scale);
+  }
+
+ private:
+  HValue* ConvertGuarantee(HValue* guarantee);
+
+  template <class T> void swap(T* a, T* b) {
+    T c(*a);
+    *a = *b;
+    *b = c;
+  }
+
+  HValue* lower_bound_;
+  HValue* lower_check_guarantee_;
+  HValue* candidate_;
+  HValue* upper_bound_;
+  HValue* upper_check_guarantee_;
+  int offset_;
+  int scale_;
+};
+
+
 typedef EnumSet<GVNFlag> GVNFlagSet;
 
 
@@ -973,25 +1058,32 @@ class HValue: public ZoneObject {
   virtual void Verify() = 0;
 #endif
 
-  // This method is recursive but it is guaranteed to terminate because
-  // RedefinedOperand() always dominates "this".
-  bool IsRelationTrue(NumericRelation relation, HValue* other) {
-    if (this == other) {
-      return NumericRelation::Eq().Implies(relation);
-    }
+  bool IsRelationTrue(NumericRelation relation,
+                      HValue* other,
+                      int offset = 0,
+                      int scale = 0);
 
-    bool result = IsRelationTrueInternal(relation, other) ||
-        other->IsRelationTrueInternal(relation.Reversed(), this);
-    if (!result) {
-      HValue* redefined = RedefinedOperand();
-      if (redefined != NULL) {
-        result = redefined->IsRelationTrue(relation, other);
-      }
+  bool TryGuaranteeRange(HValue* upper_bound);
+  virtual bool TryDecompose(HValue** base, int* offset, int* scale) {
+    if (RedefinedOperand() != NULL) {
+      return RedefinedOperand()->TryDecompose(base, offset, scale);
+    } else {
+      return false;
     }
-    return result;
   }
 
  protected:
+  void TryGuaranteeRangeRecursive(RangeEvaluationContext* context);
+
+  enum RangeGuaranteeDirection {
+    DIRECTION_NONE = 0,
+    DIRECTION_UPPER = 1,
+    DIRECTION_LOWER = 2,
+    DIRECTION_BOTH = 4

[Jakob Kummerow, 2013/03/14 12:50:09]

Looks like you're not using DIRECTION_BOTH anywhere, but if you were, you'd
probably want DIRECTION_BOTH == DIRECTION_LOWER | DIRECTION_UPPER, so it must be
3.

[Massi, 2013/03/14 15:07:18]

Done.

+  };
+  virtual void SetResponsibilityForRange(RangeGuaranteeDirection direction) {}
+  virtual void TryGuaranteeRangeChanging(RangeEvaluationContext* context) {}
+
   // This function must be overridden for instructions with flag kUseGVN, to
   // compare the non-Operand parts of the instruction.
   virtual bool DataEquals(HValue* other) {
@@ -1055,7 +1147,12 @@ class HValue: public ZoneObject {
 
   // Informative definitions can override this method to state any numeric
   // relation they provide on the redefined value.
-  virtual bool IsRelationTrueInternal(NumericRelation relation, HValue* other) {
+  // Returns true if it is guaranteed that:
+  // ((this + offset) >> scale) relation other
+  virtual bool IsRelationTrueInternal(NumericRelation relation,
+                                      HValue* other,
+                                      int offset = 0,
+                                      int scale = 0) {
     return false;
   }
 
@@ -1304,9 +1401,11 @@ class HNumericConstraint : public HTemplateInstruction<2> {
   virtual void PrintDataTo(StringStream* stream);
 
   virtual bool IsRelationTrueInternal(NumericRelation other_relation,
-                                      HValue* other_related_value) {
+                                      HValue* other_related_value,
+                                      int offset = 0,
+                                      int scale = 0) {
     if (related_value() == other_related_value) {
-      return relation().Implies(other_relation);
+      return relation().CompoundImplies(other_relation, offset, scale);
     } else {
       return false;
     }
@@ -1321,7 +1420,6 @@ class HNumericConstraint : public HTemplateInstruction<2> {
       : relation_(relation) {
     SetOperandAt(0, constrained_value);
     SetOperandAt(1, related_value);
-    set_representation(constrained_value->representation());
   }
 
   NumericRelation relation_;
@@ -2959,7 +3057,10 @@ class HPhi: public HValue {
     inputs_[index] = value;
   }
 
-  virtual bool IsRelationTrueInternal(NumericRelation relation, HValue* other);
+  virtual bool IsRelationTrueInternal(NumericRelation relation,
+                                      HValue* other,
+                                      int offset = 0,
+                                      int scale = 0);
 
  private:
   ZoneList<HValue*> inputs_;
@@ -2991,9 +3092,11 @@ class HInductionVariableAnnotation : public HUnaryOperation {
   virtual void PrintDataTo(StringStream* stream);
 
   virtual bool IsRelationTrueInternal(NumericRelation other_relation,
-                                      HValue* other_related_value) {
+                                      HValue* other_related_value,
+                                      int offset = 0,
+                                      int scale = 0) {
     if (induction_base() == other_related_value) {
-      return relation().Implies(other_relation);
+      return relation().CompoundImplies(other_relation, offset, scale);
     } else {
       return false;
     }
@@ -3007,7 +3110,6 @@ class HInductionVariableAnnotation : public HUnaryOperation {
                                int operand_index)
       : HUnaryOperation(phi),
     phi_(phi), relation_(relation), operand_index_(operand_index) {
-    set_representation(phi->representation());
   }
 
   // We need to store the phi both here and in the instruction operand because
@@ -3382,8 +3484,13 @@ enum BoundsCheckKeyMode {
 };
 
 
+class HBoundsCheckBaseIndexInformation;
+
+
 class HBoundsCheck: public HTemplateInstruction<2> {
  public:
+  friend class HBoundsCheckBaseIndexInformation;

[Jakob Kummerow, 2013/03/14 12:50:09]

Friend declarations should always be in the "private:" section
(http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Declar...)

[Massi, 2013/03/14 15:07:18]

Done (in the "protected:" section).

+
   // Normally HBoundsCheck should be created using the
   // HGraphBuilder::AddBoundsCheck() helper, which also guards the index with
   // a HCheckSmiOrInt32 check.
@@ -3393,7 +3500,9 @@ class HBoundsCheck: public HTemplateInstruction<2> {
                HValue* length,
                BoundsCheckKeyMode key_mode = DONT_ALLOW_SMI_KEY,
                Representation r = Representation::None())
-      : key_mode_(key_mode), skip_check_(false) {
+    : key_mode_(key_mode), skip_check_(false),
+      base_(NULL), offset_(0), scale_(0),
+      responsibility_direction_(DIRECTION_NONE) {
     SetOperandAt(0, index);
     SetOperandAt(1, length);
     if (r.IsNone()) {
@@ -3410,6 +3519,35 @@ class HBoundsCheck: public HTemplateInstruction<2> {
 
   bool skip_check() { return skip_check_; }
   void set_skip_check(bool skip_check) { skip_check_ = skip_check; }
+  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;
+  }
+
+  void ApplyIndexChange();
+  bool DetectCompoundIndex() {
+    ASSERT(base() == NULL);
+
+    HValue* index_base = NULL;
+    int index_offset = 0;
+    int index_scale = 0;
+    if (index()->TryDecompose(&index_base, &index_offset, &index_scale)) {
+      base_ = index_base;
+      offset_ = index_offset;
+      scale_ = index_scale;
+      return true;
+    } else {
+      base_ = index();
+      offset_ = 0;
+      scale_ = 0;
+      return false;
+    }
+  }
 
   virtual Representation RequiredInputRepresentation(int arg_index) {
     return representation();
@@ -3419,7 +3557,9 @@ class HBoundsCheck: public HTemplateInstruction<2> {
   }
 
   virtual bool IsRelationTrueInternal(NumericRelation relation,
-                                      HValue* related_value);
+                                      HValue* related_value,
+                                      int offset = 0,
+                                      int scale = 0);
 
   virtual void PrintDataTo(StringStream* stream);
   virtual void InferRepresentation(HInferRepresentation* h_infer);
@@ -3434,9 +3574,61 @@ class HBoundsCheck: public HTemplateInstruction<2> {
   DECLARE_CONCRETE_INSTRUCTION(BoundsCheck)
 
  protected:
+  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_;
+};
+
+
+class HBoundsCheckBaseIndexInformation: public HTemplateInstruction<2> {
+ public:
+  explicit HBoundsCheckBaseIndexInformation(HBoundsCheck* check) {
+    HValue* base = NULL;
+    int offset = 0;
+    int scale = 0;
+    if (check->index()->TryDecompose(&base, &offset, &scale)) {
+      SetOperandAt(0, base);
+      SetOperandAt(1, check);
+    } else {
+      UNREACHABLE();
+    }
+  }
+
+  HValue* base_index() { return OperandAt(0); }
+  HBoundsCheck* bounds_check() { return HBoundsCheck::cast(OperandAt(1)); }
+
+  DECLARE_CONCRETE_INSTRUCTION(BoundsCheckBaseIndexInformation)
+
+  virtual Representation RequiredInputRepresentation(int arg_index) {
+    return representation();
+  }
+
+  virtual bool IsRelationTrueInternal(NumericRelation relation,
+                                      HValue* related_value,
+                                      int offset = 0,
+                                      int scale = 0);
+  virtual void PrintDataTo(StringStream* stream);
+
+  virtual int RedefinedOperandIndex() { return 0; }
+  virtual bool IsPurelyInformativeDefinition() { return true; }
+
+ protected:
+  virtual void SetResponsibilityForRange(RangeGuaranteeDirection direction) {
+    bounds_check()->SetResponsibilityForRange(direction);
+  }
+  virtual void TryGuaranteeRangeChanging(RangeEvaluationContext* context) {
+    bounds_check()->TryGuaranteeRangeChanging(context);
+  }
 };
 
 
@@ -4012,21 +4204,18 @@ class HAdd: public HArithmeticBinaryOperation {
 
   virtual HValue* Canonicalize();
 
-  virtual bool IsRelationTrueInternal(NumericRelation relation, HValue* other) {
-    HValue* base = NULL;
-    int32_t offset = 0;
+  virtual bool TryDecompose(HValue** base, int* offset, int* scale) {
     if (left()->IsInteger32Constant()) {
-      base = right();
-      offset = left()->GetInteger32Constant();
+      *base = right();
+      *offset += left()->GetInteger32Constant();
+      return true;
     } else if (right()->IsInteger32Constant()) {
-      base = left();
-      offset = right()->GetInteger32Constant();
+      *base = left();
+      *offset += right()->GetInteger32Constant();
+      return true;
     } else {
       return false;
     }
-
-    return relation.IsExtendable(offset)
-        ? base->IsRelationTrue(relation, other) : false;
   }
 
   DECLARE_CONCRETE_INSTRUCTION(Add)
@@ -4054,12 +4243,11 @@ class HSub: public HArithmeticBinaryOperation {
                                HValue* left,
                                HValue* right);
 
-  virtual bool IsRelationTrueInternal(NumericRelation relation, HValue* other) {
+  virtual bool TryDecompose(HValue** base, int* offset, int* scale) {
     if (right()->IsInteger32Constant()) {
-      HValue* base = left();
-      int32_t offset = right()->GetInteger32Constant();
-      return relation.IsExtendable(-offset)
-          ? base->IsRelationTrue(relation, other) : false;
+      *base = left();
+      *offset -= right()->GetInteger32Constant();
+      return true;
     } else {
       return false;
     }
@@ -4299,6 +4487,21 @@ class HSar: public HBitwiseBinaryOperation {
 
   virtual Range* InferRange(Zone* zone);
 
+  virtual bool TryDecompose(HValue** base, int* offset, int* scale) {
+    if (!scale != 0) return false;

[Jakob Kummerow, 2013/03/14 12:50:09]

I think you mean s/!scale/*scale/.

Please add a test case that would have caught this.

[Massi, 2013/03/14 15:07:18]

Done, but with a small refactoring.

+
+    if (right()->IsInteger32Constant()) {
+      *base = left();
+      *scale = right()->GetInteger32Constant();
+      // Note that this call can change *base again, this is intended to
+      // also take HAdd and HSub effects on offset into account.
+      (*base)->TryDecompose(base, offset, scale);
+      return true;
+    } else {
+      return false;
+    }
+  }
+
   static HInstruction* NewHSar(Zone* zone,
                                HValue* context,
                                HValue* left,