| // 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) |
| : CustomMatcherZoneHashMap(BoundsCheckKeyMatch, |
| ZoneHashMap::kDefaultHashMapCapacity, |
| ZoneAllocationPolicy(zone)) {} |
| |
| BoundsCheckBbData** BoundsCheckTable::LookupOrInsert(BoundsCheckKey* key, |
| Zone* zone) { |
| return reinterpret_cast<BoundsCheckBbData**>( |
| &(CustomMatcherZoneHashMap::LookupOrInsert(key, key->Hash(), |
| ZoneAllocationPolicy(zone)) |
| ->value)); |
| } |
| |
| |
| void BoundsCheckTable::Insert(BoundsCheckKey* key, |
| BoundsCheckBbData* data, |
| Zone* zone) { |
| CustomMatcherZoneHashMap::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 |