New array bounds check elimination pass (focused on induction variables and bitwise operations).

src/hydrogen-instructions.h

Index: src/hydrogen-instructions.h
diff --git a/src/hydrogen-instructions.h b/src/hydrogen-instructions.h
index 7554fd85bad5a136e387698eb704159008be7bdd..a6ab386bbe8ac1140cb72a3e52bc4e66f3e10739 100644
--- a/src/hydrogen-instructions.h
+++ b/src/hydrogen-instructions.h
@@ -39,6 +39,7 @@
 #include "v8utils.h"
 #include "zone.h"
 
+
 namespace v8 {
 namespace internal {
 
@@ -3050,12 +3051,244 @@ class HCheckPrototypeMaps: public HTemplateInstruction<0> {
 };
 
 
+class InductionVariableData;

[titzer, 2013/06/24 14:03:30]

It seems like the only reason that all this code lives in this header file is so
that you can hang it directly off the HPhi instruction. I think we can avoid
that entanglement if we have a side table (essentially HashMap<Phi,
InductionVariableData> in the array bounds check elimination class (which should
be in its own file).

[Massi, 2013/07/01 13:10:49]

As discussed off line with danno, we can keep the reference in HPhi (having
induction variable info can will be useful elsewhere, for instance for
prefetching in indexed loads).

+
+
+struct InductionVariableLimitUpdate {
+  InductionVariableData* updated_variable;
+  HValue* limit;
+  bool limit_is_upper;
+  bool limit_is_included;
+
+  InductionVariableLimitUpdate()
+      : updated_variable(NULL), limit(NULL),
+        limit_is_upper(false), limit_is_included(false) {}
+};
+
+
+class HBoundsCheck;
+class HPhi;
+class HConstant;
+class HBitwise;
+
+
+class InductionVariableData : public ZoneObject {
+ public:
+  class InductionVariableCheck : public ZoneObject {
+   public:
+    HBoundsCheck* check() { return check_; }
+    InductionVariableCheck* next() { return next_; }
+    bool HasUpperLimit() { return upper_limit_ >= 0; }
+    int32_t upper_limit() {
+      ASSERT(HasUpperLimit());
+      return upper_limit_;
+    }
+    void set_upper_limit(int32_t upper_limit) {
+      upper_limit_ = upper_limit;
+    }
+
+    bool processed() { return processed_; }
+    void set_processed() { processed_ = true; }
+
+    InductionVariableCheck(HBoundsCheck* check,
+                           InductionVariableCheck* next,
+                           int32_t upper_limit = kNoLimit)
+        : check_(check), next_(next), upper_limit_(upper_limit),
+          processed_(false) {}
+
+   private:
+    HBoundsCheck* check_;
+    InductionVariableCheck* next_;
+    int32_t upper_limit_;
+    bool processed_;
+  };
+
+  class ChecksRelatedToLength : public ZoneObject {
+   public:
+    HValue* length() { return length_; }
+    ChecksRelatedToLength* next() { return next_; }
+    InductionVariableCheck* checks() { return checks_; }
+
+    void AddCheck(HBoundsCheck* check, int32_t upper_limit = kNoLimit);
+    void CloseCurrentBlock();
+
+    ChecksRelatedToLength(HValue* length, ChecksRelatedToLength* next)
+      : length_(length), next_(next), checks_(NULL),
+        first_check_in_block_(NULL),
+        added_index_(NULL),
+        added_constant_(NULL),
+        current_and_mask_in_block_(0),
+        current_or_mask_in_block_(0) {}
+
+   private:
+    void UseNewIndexInCurrentBlock(Token::Value token,
+                                   int32_t mask,
+                                   HValue* index_base,
+                                   HValue* context);
+
+    HBoundsCheck* first_check_in_block() { return first_check_in_block_; }
+    HBitwise* added_index() { return added_index_; }
+    HConstant* added_constant() { return added_constant_; }
+    int32_t current_and_mask_in_block() { return current_and_mask_in_block_; }
+    int32_t current_or_mask_in_block() { return current_or_mask_in_block_; }
+    int32_t current_upper_limit() { return current_upper_limit_; }
+
+    HValue* length_;
+    ChecksRelatedToLength* next_;
+    InductionVariableCheck* checks_;
+
+    HBoundsCheck* first_check_in_block_;
+    HBitwise* added_index_;
+    HConstant* added_constant_;
+    int32_t current_and_mask_in_block_;
+    int32_t current_or_mask_in_block_;
+    int32_t current_upper_limit_;
+  };
+
+  static const int32_t kNoLimit = -1;
+
+  static InductionVariableData* New(HPhi* phi);
+  static bool ComputeInductionVariableLimit(
+      HBasicBlock* block,
+      InductionVariableLimitUpdate* additional_limit);
+
+  static HValue* DecomposeBitwise(HValue* value,
+                                  int32_t* and_mask,
+                                  int32_t* or_mask,
+                                  HValue** context);
+
+  void AddCheck(HBoundsCheck* check, int32_t upper_limit = kNoLimit);
+
+  bool CheckIfBranchIsLoopGuard(HBasicBlock* in_branch,
+                                HBasicBlock* out_branch);
+
+  void UpdateAdditionalLimit(InductionVariableLimitUpdate* update) {
+    ASSERT(update->updated_variable == this);
+    if (update->limit_is_upper) {
+      swap(&additional_upper_limit_, &update->limit);
+      swap(&additional_upper_limit_is_included_, &update->limit_is_included);
+    } else {
+      swap(&additional_lower_limit_, &update->limit);
+      swap(&additional_lower_limit_is_included_, &update->limit_is_included);
+    }
+  }
+
+  HPhi* phi() { return phi_; }
+  HValue* base() { return base_; }
+  int32_t increment() { return increment_; }
+  HValue* limit() { return limit_; }
+  bool limit_included() { return limit_included_; }
+  HBasicBlock* limit_validity() { return limit_validity_; }
+  HBasicBlock* induction_exit_block() { return induction_exit_block_; }
+  HBasicBlock* induction_exit_target() { return induction_exit_target_; }
+  ChecksRelatedToLength* checks() { return checks_; }
+  HValue* additional_upper_limit() { return additional_upper_limit_; }
+  bool additional_upper_limit_is_included() {
+    return additional_upper_limit_is_included_;
+  }
+  HValue* additional_lower_limit() { return additional_lower_limit_; }
+  bool additional_lower_limit_is_included() {
+    return additional_lower_limit_is_included_;
+  }
+
+  bool lower_limit_is_non_negative_constant() {
+    if (base()->IsInteger32Constant() && base()->GetInteger32Constant() >= 0) {
+      return true;
+    }
+    if (additional_lower_limit() != NULL &&
+        additional_lower_limit()->IsInteger32Constant() &&
+        additional_lower_limit()->GetInteger32Constant() >= 0) {
+      // Ignoring the corner case of !additional_lower_limit_is_included()
+      // is safe, handling it adds unneeded complexity.
+      return true;
+    }
+    return false;
+  }
+
+  int32_t ComputeUpperLimit(int32_t and_mask, int32_t or_mask) {
+    // Should be Smi::kMaxValue but it must fit 32 bits; lower is safe anyway.
+    const int32_t MAX_LIMIT = 1 << 30;
+
+    int32_t result = MAX_LIMIT;
+
+    if (limit() != NULL &&
+        limit()->IsInteger32Constant()) {
+      int32_t limit_value = limit()->GetInteger32Constant();
+      if (!limit_included()) {
+        limit_value--;
+      }
+      if (limit_value < result) result = limit_value;
+    }
+
+    if (additional_upper_limit() != NULL &&
+        additional_upper_limit()->IsInteger32Constant()) {
+      int32_t limit_value = additional_upper_limit()->GetInteger32Constant();
+      if (!additional_upper_limit_is_included()) {
+        limit_value--;
+      }
+      if (limit_value < result) result = limit_value;
+    }
+
+    if (and_mask > 0 && and_mask < MAX_LIMIT) {
+      if (and_mask < result) result = and_mask;
+      return result;
+    }
+
+    // Add the effect of the or_mask.
+    result |= or_mask;
+
+    if (result >= MAX_LIMIT) {
+      result = kNoLimit;
+    }
+    return result;
+  }
+
+ private:
+  template <class T> void swap(T* a, T* b) {
+    T c(*a);
+    *a = *b;
+    *b = c;
+  }
+
+  InductionVariableData(HPhi* phi, HValue* base, int32_t increment)
+      : phi_(phi), base_(DiscardOsrValue(base)), increment_(increment),
+        limit_(NULL), limit_included_(false), limit_validity_(NULL),
+        induction_exit_block_(NULL), induction_exit_target_(NULL),
+        checks_(NULL),
+        additional_upper_limit_(NULL),
+        additional_upper_limit_is_included_(false),
+        additional_lower_limit_(NULL),
+        additional_lower_limit_is_included_(false) {}
+
+  static int32_t ComputeIncrement(HPhi* phi, HValue* phi_operand);
+
+  static HValue* DiscardOsrValue(HValue* v);
+  static InductionVariableData* GetInductionVariableData(HValue* v);
+  bool ValidateToken(Token::Value token);
+
+  HPhi* phi_;
+  HValue* base_;
+  int32_t increment_;
+  HValue* limit_;
+  bool limit_included_;
+  HBasicBlock* limit_validity_;
+  HBasicBlock* induction_exit_block_;
+  HBasicBlock* induction_exit_target_;
+  ChecksRelatedToLength* checks_;
+  HValue* additional_upper_limit_;
+  bool additional_upper_limit_is_included_;
+  HValue* additional_lower_limit_;
+  bool additional_lower_limit_is_included_;
+};
+
+
 class HPhi: public HValue {
  public:
   HPhi(int merged_index, Zone* zone)
       : inputs_(2, zone),
         merged_index_(merged_index),
-        phi_id_(-1) {
+        phi_id_(-1),
+        induction_variable_data_(NULL) {
     for (int i = 0; i < Representation::kNumRepresentations; i++) {
       non_phi_uses_[i] = 0;
       indirect_uses_[i] = 0;
@@ -3086,6 +3319,21 @@ class HPhi: public HValue {
 
   int merged_index() const { return merged_index_; }
 
+  InductionVariableData* induction_variable_data() {
+    return induction_variable_data_;
+  }
+  bool IsInductionVariable() {
+    return induction_variable_data_ != NULL;
+  }
+  bool IsLimitedInductionVariable() {
+    return IsInductionVariable() &&
+        induction_variable_data_->limit() != NULL;
+  }
+  void DetectInductionVariable() {
+    ASSERT(induction_variable_data_ == NULL);
+    induction_variable_data_ = InductionVariableData::New(this);
+  }
+
   virtual void AddInformativeDefinitions();
 
   virtual void PrintTo(StringStream* stream);
@@ -3153,6 +3401,7 @@ class HPhi: public HValue {
   int non_phi_uses_[Representation::kNumRepresentations];
   int indirect_uses_[Representation::kNumRepresentations];
   int phi_id_;
+  InductionVariableData* induction_variable_data_;
 };
 
 
@@ -3660,15 +3909,16 @@ class HBoundsCheck: public HTemplateInstruction<2> {
   HBoundsCheck(HValue* index, HValue* length)
     : 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);
     SetFlag(kFlexibleRepresentation);
     SetFlag(kUseGVN);
   }
 
-  bool skip_check() { return skip_check_; }
-  void set_skip_check(bool skip_check) { skip_check_ = skip_check; }
+  bool skip_check() const { return skip_check_; }
+  void set_skip_check() { skip_check_ = true; }
   HValue* base() { return base_; }
   int offset() { return offset_; }
   int scale() { return scale_; }
@@ -3700,6 +3950,9 @@ class HBoundsCheck: public HTemplateInstruction<2> {
   virtual Representation RequiredInputRepresentation(int arg_index) {
     return representation();
   }
+  virtual bool IsDeletable() const {
+    return skip_check() && !FLAG_debug_code;
+  }
 
   virtual bool IsRelationTrueInternal(NumericRelation relation,
                                       HValue* related_value,
@@ -3711,6 +3964,8 @@ class HBoundsCheck: public HTemplateInstruction<2> {
 
   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(); }
@@ -3733,6 +3988,7 @@ class HBoundsCheck: public HTemplateInstruction<2> {
   int offset_;
   int scale_;
   RangeGuaranteeDirection responsibility_direction_;
+  bool allow_equality_;
 };
 
 
@@ -6608,7 +6864,6 @@ class HLoadFieldByIndex : public HTemplateInstruction<2> {
   virtual bool IsDeletable() const { return true; }
 };
 
-
 #undef DECLARE_INSTRUCTION
 #undef DECLARE_CONCRETE_INSTRUCTION