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

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 57 matching lines @@
   V(AllocateObject)                            \
   V(ApplyArguments)                            \
   V(ArgumentsElements)                         \
   V(ArgumentsLength)                           \
   V(ArgumentsObject)                           \
   V(ArrayLiteral)                              \
   V(Bitwise)                                   \
   V(BitNot)                                    \
   V(BlockEntry)                                \
   V(BoundsCheck)                               \
+  V(BoundsCheckBaseIndexInformation)           \
   V(Branch)                                    \
   V(CallConstantFunction)                      \
   V(CallFunction)                              \
   V(CallGlobal)                                \
   V(CallKeyed)                                 \
   V(CallKnownGlobal)                           \
   V(CallNamed)                                 \
   V(CallNew)                                   \
   V(CallRuntime)                               \
   V(CallStub)                                  \
@@ skipping 571 matching lines @@
       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;
   }
 
+  // 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) {}
 
   Kind kind_;
 };
 
 
 typedef EnumSet<GVNFlag> GVNFlagSet;
 
 
@@ skipping 104 matching lines @@
   virtual void AssumeRepresentation(Representation r);
 
   virtual bool IsConvertibleToInteger() const { return true; }
 
   HType type() const { return type_; }
   void set_type(HType new_type) {
     ASSERT(new_type.IsSubtypeOf(type_));
     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.
   // The implementation must set a flag so that it bails out in the case where
   // it would otherwise output what should be a minus zero as an int32 zero.
   // If the operation also exists in a form that takes int32 and outputs int32
   // then the operation should return its input value so that we can propagate
   // back.  There are three operations that need to propagate back to more than
   // one input.  They are phi and binary div and mul.  They always return NULL
   // and expect the caller to take care of things.
@@ skipping 165 matching lines @@
   bool IsDead() const {
     return HasNoUses() && !HasObservableSideEffects() && IsDeletable();
   }
 
 #ifdef DEBUG
   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) {
+  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;
     }
-    return result;
+
+    // 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;
+    }
   }
 
  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) {
     UNREACHABLE();
     return false;
   }
 
   virtual Representation RepresentationFromInputs() {
     return representation();
   }
@@ skipping 42 matching lines @@
       for (HUseIterator uses = input->uses(); !uses.Done(); uses.Advance()) {
         HValue* use = uses.value();
         if (TestDominance(this, use)) {
           use->SetOperandAt(uses.index(), this);
         }
       }
     }
   }
 
   // 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;
   }
 
   static GVNFlagSet AllDependsOnFlagSet() {
     GVNFlagSet result;
     // Create changes mask.
 #define ADD_FLAG(type) result.Add(kDependsOn##type);
   GVN_TRACKED_FLAG_LIST(ADD_FLAG)
   GVN_UNTRACKED_FLAG_LIST(ADD_FLAG)
 #undef ADD_FLAG
@@ skipping 228 matching lines @@
   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) {
+                                      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;
     }
   }
 
   DECLARE_CONCRETE_INSTRUCTION(NumericConstraint)
 
  private:
   HNumericConstraint(HValue* constrained_value,
                      NumericRelation relation,
@@ skipping 1632 matching lines @@
     }
     return true;
   }
 
  protected:
   virtual void DeleteFromGraph();
   virtual void InternalSetOperandAt(int index, HValue* value) {
     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_;
   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_;
@@ skipping 11 matching lines @@
 
   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) {
+                                      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;
     }
   }
 
   DECLARE_CONCRETE_INSTRUCTION(InductionVariableAnnotation)
 
  private:
   HInductionVariableAnnotation(HPhi* phi,
                                NumericRelation relation,
@@ skipping 368 matching lines @@
   virtual bool DataEquals(HValue* other) { return true; }
 };
 
 
 enum BoundsCheckKeyMode {
   DONT_ALLOW_SMI_KEY,
   ALLOW_SMI_KEY
 };
 
 
+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.
   // 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) {
+    : 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()) {
       // 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; }
+  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();
   }
   virtual Representation observed_input_representation(int index) {
     return Representation::Integer32();
   }
 
   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);
 
   HValue* index() { return OperandAt(0); }
   HValue* length() { return OperandAt(1); }
 
   virtual int RedefinedOperandIndex() { return 0; }
   virtual bool IsPurelyInformativeDefinition() { return skip_check(); }
   virtual void AddInformativeDefinitions();
 
   DECLARE_CONCRETE_INSTRUCTION(BoundsCheck)
 
  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());
+    }
+
+  }
+};
+
+
 class HBitwiseBinaryOperation: public HBinaryOperation {
  public:
   HBitwiseBinaryOperation(HValue* context, HValue* left, HValue* right)
       : HBinaryOperation(context, left, right) {
     SetFlag(kFlexibleRepresentation);
     SetFlag(kTruncatingToInt32);
     SetAllSideEffects();
   }
 
   virtual Representation RequiredInputRepresentation(int index) {
@@ skipping 552 matching lines @@
 
   static HInstruction* NewHAdd(Zone* zone,
                                HValue* context,
                                HValue* left,
                                HValue* right);
 
   virtual HType CalculateInferredType();
 
   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)
 
  protected:
   virtual bool DataEquals(HValue* other) { return true; }
 
   virtual Range* InferRange(Zone* zone);
 };
 
 
 class HSub: public HArithmeticBinaryOperation {
  public:
   HSub(HValue* context, HValue* left, HValue* right)
       : HArithmeticBinaryOperation(context, left, right) {
     SetFlag(kCanOverflow);
   }
 
   virtual HValue* EnsureAndPropagateNotMinusZero(BitVector* visited);
 
   virtual HValue* Canonicalize();
 
   static HInstruction* NewHSub(Zone* zone,
                                HValue* context,
                                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;
     }
   }
 
   DECLARE_CONCRETE_INSTRUCTION(Sub)
 
  protected:
   virtual bool DataEquals(HValue* other) { return true; }
 
@@ skipping 219 matching lines @@
 };
 
 
 class HSar: public HBitwiseBinaryOperation {
  public:
   HSar(HValue* context, HValue* left, HValue* right)
       : HBitwiseBinaryOperation(context, left, right) { }
 
   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,
                                HValue* right);
 
   DECLARE_CONCRETE_INSTRUCTION(Sar)
 
  protected:
   virtual bool DataEquals(HValue* other) { return true; }
 };
@@ skipping 1772 matching lines @@
   virtual bool IsDeletable() const { return true; }
 };
 
 
 #undef DECLARE_INSTRUCTION
 #undef DECLARE_CONCRETE_INSTRUCTION
 
 } }  // namespace v8::internal
 
 #endif  // V8_HYDROGEN_INSTRUCTIONS_H_