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..5982d3cd2f411f9b684c4213bd40c848ecb19157 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,6 +667,38 @@ class NumericRelation {
     return false;
   }
 
+  // CompoundOperandsAreCompatible returns true when
+  // "((x + my_offset) >> my_scale) rel y" implies
+  // "((x + other_offset) >> other_scale) rel y".
+  bool CompoundOperandsAreCompatible(int my_offset,

[Jakob Kummerow, 2013/03/11 11:55:02]

I don't like this name. "compatible" in what sense? How about "ComponentsImply"
instead?
Also, this should be private.

+                                     int my_scale,
+                                     int other_offset,
+                                     int other_scale) {
+    switch (kind_) {
+      case NONE: return false;
+      case EQ: return my_offset == other_offset && my_scale == other_scale;

[Jakob Kummerow, 2013/03/11 11:55:02]

let's combine identical cases, i.e.:

    switch (kind_) {
      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;
      case NONE: break;  // Fall through to UNREACHABLE().
    }

+      case GT: return my_offset <= other_offset && my_scale >= other_scale;
+      case GE: return my_offset <= other_offset && my_scale >= other_scale;
+      case LT: return my_offset >= other_offset && my_scale <= other_scale;
+      case LE: return my_offset >= other_offset && my_scale <= other_scale;
+      case NE: return my_offset == other_offset && my_scale == other_scale;
+    }
+    UNREACHABLE();
+    return false;
+  }
+
+  // CompoundOperandsAreCompatible returns true when

[Jakob Kummerow, 2013/03/11 11:55:02]

comment is about the wrong method.

+  // "((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) && CompoundOperandsAreCompatible(
+        my_offset, my_scale, other_offset, other_scale);
+  }
+
  private:
   explicit NumericRelation(Kind kind) : kind_(kind) {}
 
@@ -790,6 +823,24 @@ class HValue: public ZoneObject {
     type_ = new_type;
   }
 
+  // +++++++++++++
+  void SimplyPrint() {
+    HValue* base = NULL;
+    int offset = 0;
+    int scale = 0;
+    PrintF("%s%d(", representation().Mnemonic(), id());
+    if (TryDecompose(&base, &offset, &scale)) {
+      PrintF("(%s%d + %d) >> %d",
+             base->representation().Mnemonic(), base->id(), offset, scale);
+    } else if (IsInteger32Constant()) {
+      PrintF("CONSTANT %d", GetInteger32Constant());
+    } else {
+      PrintF("%s", Mnemonic());
+    }
+    PrintF(")");
+  }
+
+
   // An operation needs to override this function iff:
   //   1) it can produce an int32 output.
   //   2) the true value of its output can potentially be minus zero.
@@ -975,23 +1026,103 @@ class HValue: public ZoneObject {
 
   // This method is recursive but it is guaranteed to terminate because
   // RedefinedOperand() always dominates "this".
-  bool IsRelationTrue(NumericRelation relation, HValue* other) {
+  bool IsRelationTrue(

[Jakob Kummerow, 2013/03/11 11:55:02]

This method is big enough to move its implementation to the .cc file.

+      NumericRelation relation, HValue* other, int offset = 0, int scale = 0) {

[Jakob Kummerow, 2013/03/11 11:55:02]

for method/function declarations (as opposed to calls), please put every
argument on its own line (unless everything, including the method name, fits
onto a single line).

     if (this == other) {
       return NumericRelation::Eq().Implies(relation);

[Jakob Kummerow, 2013/03/11 11:55:02]

Doesn't this need updating to account for offset/scale?

[Massi, 2013/03/13 15:58:14]

No, this is a real identity check, if "this" and "other" are the same then they
are equal, and if being equal implies the required relation we return true.

     }
 
-    bool result = IsRelationTrueInternal(relation, other) ||
-        other->IsRelationTrueInternal(relation.Reversed(), this);
-    if (!result) {
-      HValue* redefined = RedefinedOperand();
-      if (redefined != NULL) {
-        result = redefined->IsRelationTrue(relation, other);
-      }
+    // Test the direct relation.
+    if (IsRelationTrueInternal(relation, other, offset, scale)) return true;
+
+    // TODO: do we need the recursive pass? We are not doing it now...
+    // If scale is 0 try the reversed relation (with the full recursive pass).
+    if (scale == 0 && other->IsRelationTrueInternal(relation.Reversed(), this,
+                                                    -offset)) return true;

[Jakob Kummerow, 2013/03/11 11:55:02]

if-statements that span multiple lines need {}. I'd format like this:
    if (scale == 0 &&
        other->IsRelationTrueInternal(relation.Reversed(), this, -offset)) {
      return true;
    }

+
+    // Try decomposition.
+    HValue* my_base = NULL;
+    int my_offset = 0;
+    int my_scale = 0;
+    if (TryDecompose(&my_base, &my_offset, &my_scale) && my_scale == 0 &&
+        my_base->IsRelationTrue(relation, other, offset + my_offset, scale)) {
+      return true;
+    }
+
+    // Pass the request to the redefined value.
+    HValue* redefined = RedefinedOperand();
+    return redefined != NULL && redefined->IsRelationTrue(relation, other,
+                                                          offset, scale);
+  }
+
+  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:
+  class RangeEvaluationContext BASE_EMBEDDED {

[Jakob Kummerow, 2013/03/11 11:55:02]

I'd prefer this to be a top-level class.

+   public:
+    HValue* lower_bound() { return lower_bound_; }
+    HValue* lower_check_guarantee() { return lower_check_guarantee_; }
+    HValue* origin() { return origin_; }
+    HValue* upper_bound() { return upper_bound_; }
+    HValue* upper_check_guarantee() { return upper_check_guarantee_; }
+    int offset() { return offset_; }
+    int scale() { return scale_; }
+
+    bool lower_check_satisfied() { return lower_check_guarantee_ != NULL; }

[Jakob Kummerow, 2013/03/11 11:55:02]

I'd prefer not to have this method, because it adds confusion to call sites:
it's not obvious that set_lower_check_guarantee(...) changes the return value of
lower_check_satisfied(). You can s/lower_check_guarantee/lower_check/, and then
just inline this: "if (lower_check() == NULL) { /*...*/; set_lower_check(...);
}"

[Massi, 2013/03/13 15:58:14]

I ended up renaming the methods, and at this point I think the code is more
readable with the helpers instead of having NULL pointers checks inlined.

+    bool upper_check_satisfied() { return upper_check_guarantee_ != NULL; }
+    bool RangeSatisfied() {

[Jakob Kummerow, 2013/03/11 11:55:02]

is_range_satisfied()

+      return lower_check_satisfied() && upper_check_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);
+    }
+
+    template <class T> void swap(T& a, T& b) {

[Jakob Kummerow, 2013/03/11 11:55:02]

Private helper function should be private (or global in utils.h).
Also, please use pointers for arguments that are modified:
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Refere...

+      T c(a); a=b; b=c;

[Jakob Kummerow, 2013/03/11 11:55:02]

nit: formatting: one statement per line, spaces around '='.

+    }
+
+    void swap_origin(HValue*& other_origin,

[Jakob Kummerow, 2013/03/11 11:55:02]

Again, all references must be const. Use pointers.

+                     int& other_offset,
+                     int& other_scale) {
+      swap(origin_, other_origin);
+      swap(offset_, other_offset);
+      swap(scale_, other_scale);
+    }
+
+    RangeEvaluationContext(HValue* value, HValue* upper);

[Jakob Kummerow, 2013/03/11 11:55:02]

nit: constructor should be before methods
(http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Declar...)

+   private:

[Jakob Kummerow, 2013/03/11 11:55:02]

nit: empty line before "private:"

+    HValue* ConvertGuarantee(HValue* guarantee);
+
+    HValue* lower_bound_;
+    HValue* lower_check_guarantee_;
+    HValue* origin_;

[Jakob Kummerow, 2013/03/11 11:55:02]

I'm not too happy with the name "origin_", it's bit too generic. Ideas:
"provable_", "candidate_", "value_in_question_".

+    HValue* upper_bound_;
+    HValue* upper_check_guarantee_;
+    int offset_;
+    int scale_;
+  };
+
+  void TryGuaranteeRangeRecursive(RangeEvaluationContext* context);
+  virtual void TryGuaranteeRangeInner(RangeEvaluationContext* context) {
+
+    if (FLAG_log_abcd) {
+      PrintF(" !!! TryGuaranteeRangeInner(%s%d:%s): DEFAULT\n",
+             representation().Mnemonic(), id(), Mnemonic());
+    }
+
+  }
+
   // 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 +1186,8 @@ class HValue: public ZoneObject {
 
   // Informative definitions can override this method to state any numeric
   // relation they provide on the redefined value.

[Jakob Kummerow, 2013/03/11 11:55:02]

Please extend this comment:
// Returns true if it is guaranteed that:
// ((this + offset) >> scale) relation other

-  virtual bool IsRelationTrueInternal(NumericRelation relation, HValue* other) {
+  virtual bool IsRelationTrueInternal(NumericRelation relation, HValue* other,

[Jakob Kummerow, 2013/03/11 11:55:02]

for method/function declarations (as opposed to calls), please put every
argument on its own line (unless everything, including the method name, fits
onto a single line).

+                                      int offset = 0, int scale = 0) {
     return false;
   }
 
@@ -1304,9 +1436,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;
     }
@@ -2959,7 +3093,8 @@ class HPhi: public HValue {
     inputs_[index] = value;
   }
 
-  virtual bool IsRelationTrueInternal(NumericRelation relation, HValue* other);
+  virtual bool IsRelationTrueInternal(

[Jakob Kummerow, 2013/03/11 11:55:02]

for method/function declarations (as opposed to calls), please put every
argument on its own line (unless everything, including the method name, fits
onto a single line).

+      NumericRelation relation, HValue* other, int offset = 0, int scale = 0);
 
  private:
   ZoneList<HValue*> inputs_;
@@ -2991,9 +3126,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;
     }
@@ -3382,8 +3519,13 @@ enum BoundsCheckKeyMode {
 };
 
 
+class HBoundsCheckBaseIndexInformation;
+
+
 class HBoundsCheck: public HTemplateInstruction<2> {
  public:
+  friend class HBoundsCheckBaseIndexInformation;

[Jakob Kummerow, 2013/03/11 11:55:02]

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

+
   // Normally HBoundsCheck should be created using the
   // HGraphBuilder::AddBoundsCheck() helper, which also guards the index with
   // a HCheckSmiOrInt32 check.
@@ -3393,7 +3535,8 @@ 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),

[Jakob Kummerow, 2013/03/11 11:55:02]

let's put each initializer onto its own line.

+      base_(NULL), offset_(0), scale_(0), change_direction_(0) {
     SetOperandAt(0, index);
     SetOperandAt(1, length);
     if (r.IsNone()) {
@@ -3410,6 +3553,46 @@ 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 change_direction_ >= 0; }
+  bool index_can_decrease() { return change_direction_ <= 0; }
+  bool index_has_not_been_changed() { return change_direction_ == 0; }
+
+  void ApplyIndexChange();
+  bool DetectCompoundIndex() {
+    ASSERT(base() == NULL);

[Jakob Kummerow, 2013/03/11 11:55:02]

nit: You're using accessors ("base()") and direct member access ("base_")
alternatingly. I would prefer consistency. I don't feel strongly about which
version you choose; personally I'd go with direct member access because there's
no need to use accessors for a class's own members, and because it's consistent
with stores (where you're not using setters).

+
+    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;
+    }
+  }
+  bool HasOriginalIndex() {
+    if (base() == NULL) return true;
+
+    HValue* index_base = NULL;
+    int index_offset = 0;
+    int index_scale = 0;
+    if (index()->TryDecompose(&index_base, &index_offset, &index_scale)) {
+      ASSERT(index_base == base());
+      return index_offset == offset() && index_scale == scale();
+    } else {
+      ASSERT(index() == base());
+      return offset() == 0 && scale() == 0;
+    }
+  }
 
   virtual Representation RequiredInputRepresentation(int arg_index) {
     return representation();
@@ -3419,7 +3602,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);
@@ -3435,8 +3620,64 @@ class HBoundsCheck: public HTemplateInstruction<2> {
 
  protected:
   virtual bool DataEquals(HValue* other) { return true; }
+  virtual void TryGuaranteeRangeInner(RangeEvaluationContext* context);
   BoundsCheckKeyMode key_mode_;
   bool skip_check_;
+  HValue* base_;
+  int offset_;
+  int scale_;
+  int change_direction_;
+};
+
+
+class HBoundsCheckBaseIndexInformation: public HTemplateInstruction<2> {
+ public:
+  HBoundsCheckBaseIndexInformation(HBoundsCheck* check) {

[Jakob Kummerow, 2013/03/11 11:55:02]

explicit

+    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 TryGuaranteeRangeInner(RangeEvaluationContext* context) {
+
+    if (FLAG_log_abcd) {
+      PrintF(" !!! TryGuaranteeRangeInner(%s%d): BOUNDS INFO START\n",
+             representation().Mnemonic(), id());
+    }
+
+    bounds_check()->TryGuaranteeRangeInner(context);
+
+    if (FLAG_log_abcd) {
+      PrintF(" !!! TryGuaranteeRangeInner(%s%d): BOUNDS INFO END\n",
+             representation().Mnemonic(), id());
+    }
+
+  }
 };
 
 
@@ -4012,21 +4253,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 +4292,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 +4536,21 @@ class HSar: public HBitwiseBinaryOperation {
 
   virtual Range* InferRange(Zone* zone);
 
+  virtual bool TryDecompose(HValue** base, int* offset, int* scale) {
+    if (!scale != 0) return false;
+
+    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,