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;
   }
 
+  // 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;
 
 
 class HValue: public ZoneObject {
  public:
   static const int kNoNumber = -1;
 
   enum Flag {
     kFlexibleRepresentation,
     // Participate in Global Value Numbering, i.e. elimination of
@@ skipping 280 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) {
-    if (this == other) {
-      return NumericRelation::Eq().Implies(relation);
+  bool IsRelationTrue(NumericRelation relation,
+                      HValue* other,
+                      int offset = 0,
+                      int scale = 0);
+
+  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;
     }
-
-    bool result = IsRelationTrueInternal(relation, other) ||
-        other->IsRelationTrueInternal(relation.Reversed(), this);
-    if (!result) {
-      HValue* redefined = RedefinedOperand();
-      if (redefined != NULL) {
-        result = redefined->IsRelationTrue(relation, other);
-      }
-    }
-    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) {
     UNREACHABLE();
     return false;
   }
 
   virtual Representation RepresentationFromInputs() {
     return representation();
   }
@@ skipping 43 matching lines @@
         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.
-  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;
   }
 
   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,
                      HValue* related_value)
       : relation_(relation) {
     SetOperandAt(0, constrained_value);
     SetOperandAt(1, related_value);
-    set_representation(constrained_value->representation());
   }
 
   NumericRelation relation_;
 };
 
 
 // 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> {
@@ skipping 1617 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(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,
                                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
   // 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_;
 };
 
@@ skipping 354 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/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.
   // 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),
+      base_(NULL), offset_(0), scale_(0),
+      responsibility_direction_(DIRECTION_NONE) {
     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 (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();
   }
   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 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);
+  }
+};
+
+
 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;

[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,
                                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_