diff options
Diffstat (limited to 'deps/v8/src/crankshaft/hydrogen-bce.cc')
| -rw-r--r-- | deps/v8/src/crankshaft/hydrogen-bce.cc | 477 |
1 files changed, 477 insertions, 0 deletions
diff --git a/deps/v8/src/crankshaft/hydrogen-bce.cc b/deps/v8/src/crankshaft/hydrogen-bce.cc new file mode 100644 index 0000000000..d00d8ce25c --- /dev/null +++ b/deps/v8/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 |