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

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 21 matching lines @@
 
 #include "allocation.h"
 #include "code-stubs.h"
 #include "data-flow.h"
 #include "small-pointer-list.h"
 #include "string-stream.h"
 #include "v8conversions.h"
 #include "v8utils.h"
 #include "zone.h"
 
+
 namespace v8 {
 namespace internal {
 
 // Forward declarations.
 class HBasicBlock;
 class HEnvironment;
 class HInferRepresentation;
 class HInstruction;
 class HLoopInformation;
 class HValue;
@@ skipping 2991 matching lines @@
 
  private:
   ZoneList<Handle<JSObject> > prototypes_;
   ZoneList<Handle<Map> > maps_;
   UniqueValueId first_prototype_unique_id_;
   UniqueValueId last_prototype_unique_id_;
   bool can_omit_prototype_maps_;
 };
 
 
+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;
     }
     ASSERT(merged_index >= 0);
     SetFlag(kFlexibleRepresentation);
     SetFlag(kAllowUndefinedAsNaN);
   }
 
   virtual Representation RepresentationFromInputs();
@@ skipping 10 matching lines @@
   virtual int OperandCount() { return inputs_.length(); }
   virtual HValue* OperandAt(int index) const { return inputs_[index]; }
   HValue* GetRedundantReplacement();
   void AddInput(HValue* value);
   bool HasRealUses();
 
   bool IsReceiver() const { return merged_index_ == 0; }
 
   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);
 
 #ifdef DEBUG
   virtual void Verify();
 #endif
 
   void InitRealUses(int id);
   void AddNonPhiUsesFrom(HPhi* other);
@@ skipping 47 matching lines @@
                                       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_;
+  InductionVariableData* induction_variable_data_;
 };
 
 
 class HInductionVariableAnnotation : public HUnaryOperation {
  public:
   static HInductionVariableAnnotation* AddToGraph(HPhi* phi,
                                                   NumericRelation relation,
                                                   int operand_index);
 
   NumericRelation relation() { return relation_; }
@@ skipping 487 matching lines @@
 
 class HBoundsCheck: public HTemplateInstruction<2> {
  public:
   // Normally HBoundsCheck should be created using the
   // HGraphBuilder::AddBoundsCheck() helper.
   // 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)
     : 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_; }
   bool index_can_increase() {
     return (responsibility_direction_ & DIRECTION_LOWER) == 0;
   }
   bool index_can_decrease() {
     return (responsibility_direction_ & DIRECTION_UPPER) == 0;
   }
 
@@ skipping 11 matching lines @@
       base_ = index();
       offset_ = 0;
       scale_ = 0;
       return false;
     }
   }
 
   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,
                                       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); }
+  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(); }
   virtual void AddInformativeDefinitions();
 
   DECLARE_CONCRETE_INSTRUCTION(BoundsCheck)
 
  protected:
   friend class HBoundsCheckBaseIndexInformation;
 
   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);
   bool skip_check_;
   HValue* base_;
   int offset_;
   int scale_;
   RangeGuaranteeDirection responsibility_direction_;
+  bool allow_equality_;
 };
 
 
 class HBoundsCheckBaseIndexInformation: public HTemplateInstruction<2> {
  public:
   explicit HBoundsCheckBaseIndexInformation(HBoundsCheck* check) {
     DecompositionResult decomposition;
     if (check->index()->TryDecompose(&decomposition)) {
       SetOperandAt(0, decomposition.base());
       SetOperandAt(1, check);
@@ skipping 2855 matching lines @@
   virtual HType CalculateInferredType() {
     return HType::Tagged();
   }
 
   DECLARE_CONCRETE_INSTRUCTION(LoadFieldByIndex);
 
  private:
   virtual bool IsDeletable() const { return true; }
 };
 
-
 #undef DECLARE_INSTRUCTION
 #undef DECLARE_CONCRETE_INSTRUCTION
 
 } }  // namespace v8::internal
 
 #endif  // V8_HYDROGEN_INSTRUCTIONS_H_