Move Hydrogen and Lithium to src/crankshaft/

src/hydrogen-bce.cc

Index: src/hydrogen-bce.cc
diff --git a/src/hydrogen-bce.cc b/src/hydrogen-bce.cc
deleted file mode 100644
index 30c218f82a01834c00b0de9a5f30b2e9f7f34e82..0000000000000000000000000000000000000000
--- a/src/hydrogen-bce.cc
+++ /dev/null
@@ -1,477 +0,0 @@
-// Copyright 2013 the V8 project authors. All rights reserved.
-// Use of this source code is governed by a BSD-style license that can be
-// found in the LICENSE file.
-
-#include "src/hydrogen-bce.h"
-
-namespace v8 {
-namespace internal {
-
-
-// We try to "factor up" HBoundsCheck instructions towards the root of the
-// dominator tree.
-// For now we handle checks where the index is like "exp + int32value".
-// If in the dominator tree we check "exp + v1" and later (dominated)
-// "exp + v2", if v2 <= v1 we can safely remove the second check, and if
-// v2 > v1 we can use v2 in the 1st check and again remove the second.
-// To do so we keep a dictionary of all checks where the key if the pair
-// "exp, length".
-// The class BoundsCheckKey represents this key.
-class BoundsCheckKey : public ZoneObject {
- public:
-  HValue* IndexBase() const { return index_base_; }
-  HValue* Length() const { return length_; }
-
-  uint32_t Hash() {
-    return static_cast<uint32_t>(index_base_->Hashcode() ^ length_->Hashcode());
-  }
-
-  static BoundsCheckKey* Create(Zone* zone,
-                                HBoundsCheck* check,
-                                int32_t* offset) {
-    if (!check->index()->representation().IsSmiOrInteger32()) return NULL;
-
-    HValue* index_base = NULL;
-    HConstant* constant = NULL;
-    bool is_sub = false;
-
-    if (check->index()->IsAdd()) {
-      HAdd* index = HAdd::cast(check->index());
-      if (index->left()->IsConstant()) {
-        constant = HConstant::cast(index->left());
-        index_base = index->right();
-      } else if (index->right()->IsConstant()) {
-        constant = HConstant::cast(index->right());
-        index_base = index->left();
-      }
-    } else if (check->index()->IsSub()) {
-      HSub* index = HSub::cast(check->index());
-      is_sub = true;
-      if (index->right()->IsConstant()) {
-        constant = HConstant::cast(index->right());
-        index_base = index->left();
-      }
-    } else if (check->index()->IsConstant()) {
-      index_base = check->block()->graph()->GetConstant0();
-      constant = HConstant::cast(check->index());
-    }
-
-    if (constant != NULL && constant->HasInteger32Value() &&
-        constant->Integer32Value() != kMinInt) {
-      *offset = is_sub ? - constant->Integer32Value()
-                       : constant->Integer32Value();
-    } 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) { }
-
-  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"
-// (the key is BoundsCheckKey).
-// We scan the code with a dominator tree traversal.
-// Traversing the dominator tree we keep a stack (implemented as a singly
-// linked list) of "data" for each basic block that contains a relevant check
-// with the same key (the dictionary holds the head of the list).
-// We also keep all the "data" created for a given basic block in a list, and
-// use it to "clean up" the dictionary when backtracking in the dominator tree
-// traversal.
-// Doing this each dictionary entry always directly points to the check that
-// is dominating the code being examined now.
-// We also track the current "offset" of the index expression and use it to
-// decide if any check is already "covered" (so it can be removed) or not.
-class BoundsCheckBbData: public ZoneObject {
- public:
-  BoundsCheckKey* Key() const { return key_; }
-  int32_t LowerOffset() const { return lower_offset_; }
-  int32_t UpperOffset() const { return upper_offset_; }
-  HBasicBlock* BasicBlock() const { return basic_block_; }
-  HBoundsCheck* LowerCheck() const { return lower_check_; }
-  HBoundsCheck* UpperCheck() const { return upper_check_; }
-  BoundsCheckBbData* NextInBasicBlock() const { return next_in_bb_; }
-  BoundsCheckBbData* FatherInDominatorTree() const { return father_in_dt_; }
-
-  bool OffsetIsCovered(int32_t offset) const {
-    return offset >= LowerOffset() && offset <= UpperOffset();
-  }
-
-  bool HasSingleCheck() { return lower_check_ == upper_check_; }
-
-  void UpdateUpperOffsets(HBoundsCheck* check, int32_t offset) {
-    BoundsCheckBbData* data = FatherInDominatorTree();
-    while (data != NULL && data->UpperCheck() == check) {
-      DCHECK(data->upper_offset_ < offset);
-      data->upper_offset_ = offset;
-      data = data->FatherInDominatorTree();
-    }
-  }
-
-  void UpdateLowerOffsets(HBoundsCheck* check, int32_t offset) {
-    BoundsCheckBbData* data = FatherInDominatorTree();
-    while (data != NULL && data->LowerCheck() == check) {
-      DCHECK(data->lower_offset_ > offset);
-      data->lower_offset_ = offset;
-      data = data->FatherInDominatorTree();
-    }
-  }
-
-  // The goal of this method is to modify either upper_offset_ or
-  // lower_offset_ so that also new_offset is covered (the covered
-  // 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.
-  void CoverCheck(HBoundsCheck* new_check,
-                  int32_t new_offset) {
-    DCHECK(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 {
-        TightenCheck(upper_check_, new_check, new_offset);
-        UpdateUpperOffsets(upper_check_, upper_offset_);
-      }
-    } else if (new_offset < lower_offset_) {
-      lower_offset_ = new_offset;
-      if (HasSingleCheck()) {
-        keep_new_check = true;
-        lower_check_ = new_check;
-      } else {
-        TightenCheck(lower_check_, new_check, new_offset);
-        UpdateLowerOffsets(lower_check_, lower_offset_);
-      }
-    } else {
-      // Should never have called CoverCheck() in this case.
-      UNREACHABLE();
-    }
-
-    if (!keep_new_check) {
-      if (FLAG_trace_bce) {
-        base::OS::Print("Eliminating check #%d after tightening\n",
-                        new_check->id());
-      }
-      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_;
-      if (FLAG_trace_bce) {
-        base::OS::Print("Moving second check #%d after first check #%d\n",
-                        new_check->id(), first_check->id());
-      }
-      // The length is guaranteed to be live at first_check.
-      DCHECK(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);
-    }
-  }
-
-  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),
-        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_;
-  BoundsCheckBbData* next_in_bb_;
-  BoundsCheckBbData* father_in_dt_;
-
-  void MoveIndexIfNecessary(HValue* index_raw,
-                            HBoundsCheck* insert_before,
-                            HInstruction* end_of_scan_range) {
-    // index_raw can be HAdd(index_base, offset), HSub(index_base, offset),
-    // HConstant(offset) or index_base directly.
-    // In the latter case, no need to move anything.
-    if (index_raw->IsAdd() || index_raw->IsSub()) {
-      HArithmeticBinaryOperation* index =
-          HArithmeticBinaryOperation::cast(index_raw);
-      HValue* left_input = index->left();
-      HValue* right_input = index->right();
-      HValue* context = index->context();
-      bool must_move_index = false;
-      bool must_move_left_input = false;
-      bool must_move_right_input = false;
-      bool must_move_context = 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 == context) must_move_context = true;
-        if (cursor == index) must_move_index = true;
-        if (cursor->previous() == NULL) {
-          cursor = cursor->block()->dominator()->end();
-        } else {
-          cursor = cursor->previous();
-        }
-      }
-      if (must_move_index) {
-        index->Unlink();
-        index->InsertBefore(insert_before);
-      }
-      // 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);
-      }
-      if (must_move_right_input) {
-        HConstant::cast(right_input)->Unlink();
-        HConstant::cast(right_input)->InsertBefore(index);
-      }
-      if (must_move_context) {
-        // Contexts are always constants.
-        HConstant::cast(context)->Unlink();
-        HConstant::cast(context)->InsertBefore(index);
-      }
-    } else if (index_raw->IsConstant()) {
-      HConstant* index = HConstant::cast(index_raw);
-      bool must_move = false;
-      for (HInstruction* cursor = end_of_scan_range; cursor != insert_before;) {
-        if (cursor == index) must_move = true;
-        if (cursor->previous() == NULL) {
-          cursor = cursor->block()->dominator()->end();
-        } else {
-          cursor = cursor->previous();
-        }
-      }
-      if (must_move) {
-        index->Unlink();
-        index->InsertBefore(insert_before);
-      }
-    }
-  }
-
-  void TightenCheck(HBoundsCheck* original_check,
-                    HBoundsCheck* tighter_check,
-                    int32_t new_offset) {
-    DCHECK(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());
-    if (FLAG_trace_bce) {
-      base::OS::Print("Tightened check #%d with offset %d from #%d\n",
-                      original_check->id(), new_offset, tighter_check->id());
-    }
-  }
-
-  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();
-}
-
-
-BoundsCheckTable::BoundsCheckTable(Zone* zone)
-    : ZoneHashMap(BoundsCheckKeyMatch, ZoneHashMap::kDefaultHashMapCapacity,
-                  ZoneAllocationPolicy(zone)) { }
-
-
-BoundsCheckBbData** BoundsCheckTable::LookupOrInsert(BoundsCheckKey* key,
-                                                     Zone* zone) {
-  return reinterpret_cast<BoundsCheckBbData**>(
-      &(ZoneHashMap::LookupOrInsert(key, key->Hash(),
-                                    ZoneAllocationPolicy(zone))->value));
-}
-
-
-void BoundsCheckTable::Insert(BoundsCheckKey* key,
-                              BoundsCheckBbData* data,
-                              Zone* zone) {
-  ZoneHashMap::LookupOrInsert(key, key->Hash(), ZoneAllocationPolicy(zone))
-      ->value = data;
-}
-
-
-void BoundsCheckTable::Delete(BoundsCheckKey* key) {
-  Remove(key, key->Hash());
-}
-
-
-class HBoundsCheckEliminationState {
- public:
-  HBasicBlock* block_;
-  BoundsCheckBbData* bb_data_list_;
-  int index_;
-};
-
-
-// Eliminates checks in bb and recursively in the dominated blocks.
-// Also replace the results of check instructions with the original value, if
-// the result is used. This is safe now, since we don't do code motion after
-// this point. It enables better register allocation since the value produced
-// by check instructions is really a copy of the original value.
-void HBoundsCheckEliminationPhase::EliminateRedundantBoundsChecks(
-    HBasicBlock* entry) {
-  // Allocate the stack.
-  HBoundsCheckEliminationState* stack =
-    zone()->NewArray<HBoundsCheckEliminationState>(graph()->blocks()->length());
-
-  // Explicitly push the entry block.
-  stack[0].block_ = entry;
-  stack[0].bb_data_list_ = PreProcessBlock(entry);
-  stack[0].index_ = 0;
-  int stack_depth = 1;
-
-  // Implement depth-first traversal with a stack.
-  while (stack_depth > 0) {
-    int current = stack_depth - 1;
-    HBoundsCheckEliminationState* state = &stack[current];
-    const ZoneList<HBasicBlock*>* children = state->block_->dominated_blocks();
-
-    if (state->index_ < children->length()) {
-      // Recursively visit children blocks.
-      HBasicBlock* child = children->at(state->index_++);
-      int next = stack_depth++;
-      stack[next].block_ = child;
-      stack[next].bb_data_list_ = PreProcessBlock(child);
-      stack[next].index_ = 0;
-    } else {
-      // Finished with all children; post process the block.
-      PostProcessBlock(state->block_, state->bb_data_list_);
-      stack_depth--;
-    }
-  }
-}
-
-
-BoundsCheckBbData* HBoundsCheckEliminationPhase::PreProcessBlock(
-    HBasicBlock* bb) {
-  BoundsCheckBbData* bb_data_list = NULL;
-
-  for (HInstructionIterator it(bb); !it.Done(); it.Advance()) {
-    HInstruction* i = it.Current();
-    if (!i->IsBoundsCheck()) continue;
-
-    HBoundsCheck* check = HBoundsCheck::cast(i);
-    int32_t offset = 0;
-    BoundsCheckKey* key =
-        BoundsCheckKey::Create(zone(), check, &offset);
-    if (key == NULL) continue;
-    BoundsCheckBbData** data_p = table_.LookupOrInsert(key, zone());
-    BoundsCheckBbData* data = *data_p;
-    if (data == NULL) {
-      bb_data_list = new(zone()) BoundsCheckBbData(key,
-                                                   offset,
-                                                   offset,
-                                                   bb,
-                                                   check,
-                                                   check,
-                                                   bb_data_list,
-                                                   NULL);
-      *data_p = bb_data_list;
-      if (FLAG_trace_bce) {
-        base::OS::Print("Fresh bounds check data for block #%d: [%d]\n",
-                        bb->block_id(), offset);
-      }
-    } else if (data->OffsetIsCovered(offset)) {
-      bb->graph()->isolate()->counters()->
-          bounds_checks_eliminated()->Increment();
-      if (FLAG_trace_bce) {
-        base::OS::Print("Eliminating bounds check #%d, offset %d is covered\n",
-                        check->id(), offset);
-      }
-      check->DeleteAndReplaceWith(check->ActualValue());
-    } else if (data->BasicBlock() == bb) {
-      // TODO(jkummerow): I think the following logic would be preferable:
-      // if (data->Basicblock() == bb ||
-      //     graph()->use_optimistic_licm() ||
-      //     bb->IsLoopSuccessorDominator()) {
-      //   data->CoverCheck(check, offset)
-      // } else {
-      //   /* add pristine BCBbData like in (data == NULL) case above */
-      // }
-      // Even better would be: distinguish between read-only dominator-imposed
-      // knowledge and modifiable upper/lower checks.
-      // What happens currently is that the first bounds check in a dominated
-      // block will stay around while any further checks are hoisted out,
-      // which doesn't make sense. Investigate/fix this in a future CL.
-      data->CoverCheck(check, offset);
-    } else if (graph()->use_optimistic_licm() ||
-               bb->IsLoopSuccessorDominator()) {
-      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);
-      if (FLAG_trace_bce) {
-        base::OS::Print("Updated bounds check data for block #%d: [%d - %d]\n",
-                        bb->block_id(), new_lower_offset, new_upper_offset);
-      }
-      table_.Insert(key, bb_data_list, zone());
-    }
-  }
-
-  return bb_data_list;
-}
-
-
-void HBoundsCheckEliminationPhase::PostProcessBlock(
-    HBasicBlock* block, BoundsCheckBbData* data) {
-  while (data != NULL) {
-    if (data->FatherInDominatorTree()) {
-      table_.Insert(data->Key(), data->FatherInDominatorTree(), zone());
-    } else {
-      table_.Delete(data->Key());
-    }
-    data = data->NextInBasicBlock();
-  }
-}
-
-}  // namespace internal
-}  // namespace v8