Upgrade V8 to version 4.9.385.28
https://chromium.googlesource.com/v8/v8/+/4.9.385.28
FPIIM-449
Change-Id: I4b2e74289d4bf3667f2f3dc8aa2e541f63e26eb4
diff --git a/src/crankshaft/hydrogen-bce.cc b/src/crankshaft/hydrogen-bce.cc
new file mode 100644
index 0000000..d00d8ce
--- /dev/null
+++ b/src/crankshaft/hydrogen-bce.cc
@@ -0,0 +1,477 @@
+// 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/crankshaft/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