Fix Hydrogen bounds check elimination

src/hydrogen-bce.cc

 // Copyright 2013 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 73 matching lines @@
     } else {
       *offset = 0;
       index_base = check->index();
     }
 
     return new(zone) BoundsCheckKey(index_base, check->length());
   }
 
  private:
   BoundsCheckKey(HValue* index_base, HValue* length)
-    : index_base_(index_base),
-      length_(length) { }
+      : index_base_(index_base),
+        length_(length) { }
 
   HValue* index_base_;
   HValue* length_;
 
   DISALLOW_COPY_AND_ASSIGN(BoundsCheckKey);
 };
 
 
 // Data about each HBoundsCheck that can be eliminated or moved.
 // It is the "value" in the dictionary indexed by "base-index, length"
@@ skipping 31 matching lines @@
   // range grows).
   //
   // The precondition is that new_check follows UpperCheck() and
   // LowerCheck() in the same basic block, and that new_offset is not
   // covered (otherwise we could simply remove new_check).
   //
   // If HasSingleCheck() is true then new_check is added as "second check"
   // (either upper or lower; note that HasSingleCheck() becomes false).
   // Otherwise one of the current checks is modified so that it also covers
   // new_offset, and new_check is removed.
-  //
-  // If the check cannot be modified because the context is unknown it
-  // returns false, otherwise it returns true.
-  bool CoverCheck(HBoundsCheck* new_check,
+  void CoverCheck(HBoundsCheck* new_check,
                   int32_t new_offset) {
     ASSERT(new_check->index()->representation().IsSmiOrInteger32());
     bool keep_new_check = false;
 
     if (new_offset > upper_offset_) {
       upper_offset_ = new_offset;
       if (HasSingleCheck()) {
         keep_new_check = true;
         upper_check_ = new_check;
       } else {
-        bool result = BuildOffsetAdd(upper_check_,
-                                     &added_upper_index_,
-                                     &added_upper_offset_,
-                                     Key()->IndexBase(),
-                                     new_check->index()->representation(),
-                                     new_offset);
-        if (!result) return false;
-        upper_check_->ReplaceAllUsesWith(upper_check_->index());
-        upper_check_->SetOperandAt(0, added_upper_index_);
+        TightenCheck(upper_check_, new_check);
       }
     } else if (new_offset < lower_offset_) {
       lower_offset_ = new_offset;
       if (HasSingleCheck()) {
         keep_new_check = true;
         lower_check_ = new_check;
       } else {
-        bool result = BuildOffsetAdd(lower_check_,
-                                     &added_lower_index_,
-                                     &added_lower_offset_,
-                                     Key()->IndexBase(),
-                                     new_check->index()->representation(),
-                                     new_offset);
-        if (!result) return false;
-        lower_check_->ReplaceAllUsesWith(lower_check_->index());
-        lower_check_->SetOperandAt(0, added_lower_index_);
+        TightenCheck(lower_check_, new_check);
       }
     } else {
-      ASSERT(false);
+      // Should never have called CoverCheck() in this case.
+      UNREACHABLE();
     }
 
     if (!keep_new_check) {
       new_check->block()->graph()->isolate()->counters()->
           bounds_checks_eliminated()->Increment();
       new_check->DeleteAndReplaceWith(new_check->ActualValue());
+    } else {
+      HBoundsCheck* first_check = new_check == lower_check_ ? upper_check_
+                                                            : lower_check_;
+      // The length is guaranteed to be live at first_check.
+      ASSERT(new_check->length() == first_check->length());
+      HInstruction* old_position = new_check->next();
+      new_check->Unlink();
+      new_check->InsertAfter(first_check);
+      MoveIndexIfNecessary(new_check->index(), new_check, old_position);
     }
-
-    return true;
-  }
-
-  void RemoveZeroOperations() {
-    RemoveZeroAdd(&added_lower_index_, &added_lower_offset_);
-    RemoveZeroAdd(&added_upper_index_, &added_upper_offset_);
   }
 
   BoundsCheckBbData(BoundsCheckKey* key,
                     int32_t lower_offset,
                     int32_t upper_offset,
                     HBasicBlock* bb,
                     HBoundsCheck* lower_check,
                     HBoundsCheck* upper_check,
                     BoundsCheckBbData* next_in_bb,
                     BoundsCheckBbData* father_in_dt)
-  : key_(key),
-    lower_offset_(lower_offset),
-    upper_offset_(upper_offset),
-    basic_block_(bb),
-    lower_check_(lower_check),
-    upper_check_(upper_check),
-    added_lower_index_(NULL),
-    added_lower_offset_(NULL),
-    added_upper_index_(NULL),
-    added_upper_offset_(NULL),
-    next_in_bb_(next_in_bb),
-    father_in_dt_(father_in_dt) { }
+      : key_(key),
+        lower_offset_(lower_offset),
+        upper_offset_(upper_offset),
+        basic_block_(bb),
+        lower_check_(lower_check),
+        upper_check_(upper_check),
+        next_in_bb_(next_in_bb),
+        father_in_dt_(father_in_dt) { }
 
  private:
   BoundsCheckKey* key_;
   int32_t lower_offset_;
   int32_t upper_offset_;
   HBasicBlock* basic_block_;
   HBoundsCheck* lower_check_;
   HBoundsCheck* upper_check_;
-  HInstruction* added_lower_index_;
-  HConstant* added_lower_offset_;
-  HInstruction* added_upper_index_;
-  HConstant* added_upper_offset_;
   BoundsCheckBbData* next_in_bb_;
   BoundsCheckBbData* father_in_dt_;
 
-  // Given an existing add instruction and a bounds check it tries to
-  // find the current context (either of the add or of the check index).
-  HValue* IndexContext(HInstruction* add, HBoundsCheck* check) {
-    if (add != NULL && add->IsAdd()) {
-      return HAdd::cast(add)->context();
+  void MoveIndexIfNecessary(HValue* index_raw,
+                            HBoundsCheck* insert_before,
+                            HInstruction* end_of_scan_range) {
+    ASSERT(index_raw->IsAdd() || index_raw->IsSub());
+    HArithmeticBinaryOperation* index =
+        HArithmeticBinaryOperation::cast(index_raw);
+    HValue* left_input = index->left();
+    HValue* right_input = index->right();
+    bool must_move_index = false;
+    bool must_move_left_input = false;
+    bool must_move_right_input = false;
+    for (HInstruction* cursor = end_of_scan_range; cursor != insert_before;) {
+      if (cursor == left_input) must_move_left_input = true;
+      if (cursor == right_input) must_move_right_input = true;
+      if (cursor == index) must_move_index = true;
+      if (cursor->previous() == NULL) {
+        cursor = cursor->block()->dominator()->end();
+      } else {
+        cursor = cursor->previous();
+      }
     }
-    if (check->index()->IsBinaryOperation()) {
-      return HBinaryOperation::cast(check->index())->context();
+    if (must_move_index) {
+      index->Unlink();
+      index->InsertBefore(insert_before);
     }
-    return NULL;
-  }
-
-  // This function returns false if it cannot build the add because the
-  // current context cannot be determined.
-  bool BuildOffsetAdd(HBoundsCheck* check,
-                      HInstruction** add,
-                      HConstant** constant,
-                      HValue* original_value,
-                      Representation representation,
-                      int32_t new_offset) {
-    HValue* index_context = IndexContext(*add, check);
-    if (index_context == NULL) return false;
-
-    Zone* zone = BasicBlock()->zone();
-    HConstant* new_constant = HConstant::New(zone, index_context,
-                                             new_offset, representation);
-    if (*add == NULL) {
-      new_constant->InsertBefore(check);
-      (*add) = HAdd::New(zone, index_context, original_value, new_constant);
-      (*add)->AssumeRepresentation(representation);
-      (*add)->InsertBefore(check);
-    } else {
-      new_constant->InsertBefore(*add);
-      (*constant)->DeleteAndReplaceWith(new_constant);
+    // The BCE algorithm only selects mergeable bounds checks that share
+    // the same "index_base", so we'll only ever have to move constants.
+    if (must_move_left_input) {
+      HConstant::cast(left_input)->Unlink();
+      HConstant::cast(left_input)->InsertBefore(index);
     }
-    *constant = new_constant;
-    return true;
-  }
-
-  void RemoveZeroAdd(HInstruction** add, HConstant** constant) {
-    if (*add != NULL && (*add)->IsAdd() && (*constant)->Integer32Value() == 0) {
-      (*add)->DeleteAndReplaceWith(HAdd::cast(*add)->left());
-      (*constant)->DeleteAndReplaceWith(NULL);
+    if (must_move_right_input) {
+      HConstant::cast(right_input)->Unlink();
+      HConstant::cast(right_input)->InsertBefore(index);
     }
   }
 
+  void TightenCheck(HBoundsCheck* original_check,
+                    HBoundsCheck* tighter_check) {
+    ASSERT(original_check->length() == tighter_check->length());
+    MoveIndexIfNecessary(tighter_check->index(), original_check, tighter_check);
+    original_check->ReplaceAllUsesWith(original_check->index());
+    original_check->SetOperandAt(0, tighter_check->index());
+  }
+
   DISALLOW_COPY_AND_ASSIGN(BoundsCheckBbData);
 };
 
 
 static bool BoundsCheckKeyMatch(void* key1, void* key2) {
   BoundsCheckKey* k1 = static_cast<BoundsCheckKey*>(key1);
   BoundsCheckKey* k2 = static_cast<BoundsCheckKey*>(key2);
   return k1->IndexBase() == k2->IndexBase() && k1->Length() == k2->Length();
 }
 
@@ skipping 91 matching lines @@
                                                    bb,
                                                    check,
                                                    check,
                                                    bb_data_list,
                                                    NULL);
       *data_p = bb_data_list;
     } else if (data->OffsetIsCovered(offset)) {
       bb->graph()->isolate()->counters()->
           bounds_checks_eliminated()->Increment();
       check->DeleteAndReplaceWith(check->ActualValue());
-    } else if (data->BasicBlock() != bb ||
-               !data->CoverCheck(check, offset)) {
-      // If the check is in the current BB we try to modify it by calling
-      // "CoverCheck", but if also that fails we record the current offsets
-      // in a new data instance because from now on they are covered.
+    } else if (data->BasicBlock() == bb) {
+      data->CoverCheck(check, offset);
+    } else {
       int32_t new_lower_offset = offset < data->LowerOffset()
           ? offset
           : data->LowerOffset();
       int32_t new_upper_offset = offset > data->UpperOffset()
           ? offset
           : data->UpperOffset();
       bb_data_list = new(zone()) BoundsCheckBbData(key,
                                                    new_lower_offset,
                                                    new_upper_offset,
                                                    bb,
                                                    data->LowerCheck(),
                                                    data->UpperCheck(),
                                                    bb_data_list,
                                                    data);
       table_.Insert(key, bb_data_list, zone());
     }
   }
 
   return bb_data_list;
 }
 
 
 void HBoundsCheckEliminationPhase::PostProcessBlock(
     HBasicBlock* block, BoundsCheckBbData* data) {
   while (data != NULL) {
-    data->RemoveZeroOperations();
     if (data->FatherInDominatorTree()) {
       table_.Insert(data->Key(), data->FatherInDominatorTree(), zone());
     } else {
       table_.Delete(data->Key());
     }
     data = data->NextInBasicBlock();
   }
 }
 
 } }  // namespace v8::internal