| // 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 |
| // with the distribution. |
| // * Neither the name of Google Inc. nor the names of its |
| // contributors may be used to endorse or promote products derived |
| // from this software without specific prior written permission. |
| // |
| // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| |
| #include "hydrogen-bch.h" |
| |
| namespace v8 { |
| namespace internal { |
| |
| /* |
| * This class is a table with one element for eack basic block. |
| * |
| * It is used to check if, inside one loop, all execution paths contain |
| * a bounds check for a particular [index, length] combination. |
| * The reason is that if there is a path that stays in the loop without |
| * executing a check then the check cannot be hoisted out of the loop (it |
| * would likely fail and cause a deopt for no good reason). |
| * We also check is there are paths that exit the loop early, and if yes we |
| * perform the hoisting only if graph()->use_optimistic_licm() is true. |
| * The reason is that such paths are realtively common and harmless (like in |
| * a "search" method that scans an array until an element is found), but in |
| * some cases they could cause a deopt if we hoist the check so this is a |
| * situation we need to detect. |
| */ |
| class InductionVariableBlocksTable BASE_EMBEDDED { |
| public: |
| class Element { |
| public: |
| static const int kNoBlock = -1; |
| |
| HBasicBlock* block() { return block_; } |
| void set_block(HBasicBlock* block) { block_ = block; } |
| bool is_start() { return is_start_; } |
| bool is_proper_exit() { return is_proper_exit_; } |
| bool is_in_loop() { return is_in_loop_; } |
| bool has_check() { return has_check_; } |
| void set_has_check() { has_check_ = true; } |
| InductionVariableLimitUpdate* additional_limit() { |
| return &additional_limit_; |
| } |
| |
| /* |
| * Initializes the table element for a given loop (identified by its |
| * induction variable). |
| */ |
| void InitializeLoop(InductionVariableData* data) { |
| ASSERT(data->limit() != NULL); |
| HLoopInformation* loop = data->phi()->block()->current_loop(); |
| is_start_ = (block() == loop->loop_header()); |
| is_proper_exit_ = (block() == data->induction_exit_target()); |
| is_in_loop_ = loop->IsNestedInThisLoop(block()->current_loop()); |
| has_check_ = false; |
| } |
| |
| // Utility methods to iterate over dominated blocks. |
| void ResetCurrentDominatedBlock() { current_dominated_block_ = kNoBlock; } |
| HBasicBlock* CurrentDominatedBlock() { |
| ASSERT(current_dominated_block_ != kNoBlock); |
| return current_dominated_block_ < block()->dominated_blocks()->length() ? |
| block()->dominated_blocks()->at(current_dominated_block_) : NULL; |
| } |
| HBasicBlock* NextDominatedBlock() { |
| current_dominated_block_++; |
| return CurrentDominatedBlock(); |
| } |
| |
| Element() |
| : block_(NULL), is_start_(false), is_proper_exit_(false), |
| has_check_(false), additional_limit_(), |
| current_dominated_block_(kNoBlock) {} |
| |
| private: |
| HBasicBlock* block_; |
| bool is_start_; |
| bool is_proper_exit_; |
| bool is_in_loop_; |
| bool has_check_; |
| InductionVariableLimitUpdate additional_limit_; |
| int current_dominated_block_; |
| }; |
| |
| HGraph* graph() { return graph_; } |
| HBasicBlock* loop_header() { return loop_header_; } |
| Element* at(int index) { return &(elements_.at(index)); } |
| Element* at(HBasicBlock* block) { return at(block->block_id()); } |
| |
| void AddCheckAt(HBasicBlock* block) { |
| at(block->block_id())->set_has_check(); |
| } |
| |
| /* |
| * Initializes the table for a given loop (identified by its induction |
| * variable). |
| */ |
| void InitializeLoop(InductionVariableData* data) { |
| for (int i = 0; i < graph()->blocks()->length(); i++) { |
| at(i)->InitializeLoop(data); |
| } |
| loop_header_ = data->phi()->block()->current_loop()->loop_header(); |
| } |
| |
| |
| enum Hoistability { |
| HOISTABLE, |
| OPTIMISTICALLY_HOISTABLE, |
| NOT_HOISTABLE |
| }; |
| |
| /* |
| * This method checks if it is appropriate to hoist the bounds checks on an |
| * induction variable out of the loop. |
| * The problem is that in the loop code graph there could be execution paths |
| * where the check is not performed, but hoisting the check has the same |
| * semantics as performing it at every loop iteration, which could cause |
| * unnecessary check failures (which would mean unnecessary deoptimizations). |
| * The method returns OK if there are no paths that perform an iteration |
| * (loop back to the header) without meeting a check, or UNSAFE is set if |
| * early exit paths are found. |
| */ |
| Hoistability CheckHoistability() { |
| for (int i = 0; i < elements_.length(); i++) { |
| at(i)->ResetCurrentDominatedBlock(); |
| } |
| bool unsafe = false; |
| |
| HBasicBlock* current = loop_header(); |
| while (current != NULL) { |
| HBasicBlock* next; |
| |
| if (at(current)->has_check() || !at(current)->is_in_loop()) { |
| // We found a check or we reached a dominated block out of the loop, |
| // therefore this block is safe and we can backtrack. |
| next = NULL; |
| } else { |
| for (int i = 0; i < current->end()->SuccessorCount(); i ++) { |
| Element* successor = at(current->end()->SuccessorAt(i)); |
| |
| if (!successor->is_in_loop()) { |
| if (!successor->is_proper_exit()) { |
| // We found a path that exits the loop early, and is not the exit |
| // related to the induction limit, therefore hoisting checks is |
| // an optimistic assumption. |
| unsafe = true; |
| } |
| } |
| |
| if (successor->is_start()) { |
| // We found a path that does one loop iteration without meeting any |
| // check, therefore hoisting checks would be likely to cause |
| // unnecessary deopts. |
| return NOT_HOISTABLE; |
| } |
| } |
| |
| next = at(current)->NextDominatedBlock(); |
| } |
| |
| // If we have no next block we need to backtrack the tree traversal. |
| while (next == NULL) { |
| current = current->dominator(); |
| if (current != NULL) { |
| next = at(current)->NextDominatedBlock(); |
| } else { |
| // We reached the root: next stays NULL. |
| next = NULL; |
| break; |
| } |
| } |
| |
| current = next; |
| } |
| |
| return unsafe ? OPTIMISTICALLY_HOISTABLE : HOISTABLE; |
| } |
| |
| explicit InductionVariableBlocksTable(HGraph* graph) |
| : graph_(graph), loop_header_(NULL), |
| elements_(graph->blocks()->length(), graph->zone()) { |
| for (int i = 0; i < graph->blocks()->length(); i++) { |
| Element element; |
| element.set_block(graph->blocks()->at(i)); |
| elements_.Add(element, graph->zone()); |
| ASSERT(at(i)->block()->block_id() == i); |
| } |
| } |
| |
| // Tries to hoist a check out of its induction loop. |
| void ProcessRelatedChecks( |
| InductionVariableData::InductionVariableCheck* check, |
| InductionVariableData* data) { |
| HValue* length = check->check()->length(); |
| check->set_processed(); |
| HBasicBlock* header = |
| data->phi()->block()->current_loop()->loop_header(); |
| HBasicBlock* pre_header = header->predecessors()->at(0); |
| // Check that the limit is defined in the loop preheader. |
| if (!data->limit()->IsInteger32Constant()) { |
| HBasicBlock* limit_block = data->limit()->block(); |
| if (limit_block != pre_header && |
| !limit_block->Dominates(pre_header)) { |
| return; |
| } |
| } |
| // Check that the length and limit have compatible representations. |
| if (!(data->limit()->representation().Equals( |
| length->representation()) || |
| data->limit()->IsInteger32Constant())) { |
| return; |
| } |
| // Check that the length is defined in the loop preheader. |
| if (check->check()->length()->block() != pre_header && |
| !check->check()->length()->block()->Dominates(pre_header)) { |
| return; |
| } |
| |
| // Add checks to the table. |
| for (InductionVariableData::InductionVariableCheck* current_check = check; |
| current_check != NULL; |
| current_check = current_check->next()) { |
| if (current_check->check()->length() != length) continue; |
| |
| AddCheckAt(current_check->check()->block()); |
| current_check->set_processed(); |
| } |
| |
| // Check that we will not cause unwanted deoptimizations. |
| Hoistability hoistability = CheckHoistability(); |
| if (hoistability == NOT_HOISTABLE || |
| (hoistability == OPTIMISTICALLY_HOISTABLE && |
| !graph()->use_optimistic_licm())) { |
| return; |
| } |
| |
| // We will do the hoisting, but we must see if the limit is "limit" or if |
| // all checks are done on constants: if all check are done against the same |
| // constant limit we will use that instead of the induction limit. |
| bool has_upper_constant_limit = true; |
| InductionVariableData::InductionVariableCheck* current_check = check; |
| int32_t upper_constant_limit = |
| current_check != NULL && current_check->HasUpperLimit() ? |
| current_check->upper_limit() : 0; |
| while (current_check != NULL) { |
| if (check->HasUpperLimit()) { |
| if (check->upper_limit() != upper_constant_limit) { |
| has_upper_constant_limit = false; |
| } |
| } else { |
| has_upper_constant_limit = false; |
| } |
| |
| current_check->check()->block()->graph()->isolate()->counters()-> |
| bounds_checks_eliminated()->Increment(); |
| current_check->check()->set_skip_check(); |
| current_check = current_check->next(); |
| } |
| |
| // Choose the appropriate limit. |
| Zone* zone = graph()->zone(); |
| HValue* context = graph()->GetInvalidContext(); |
| HValue* limit = data->limit(); |
| if (has_upper_constant_limit) { |
| HConstant* new_limit = HConstant::New(zone, context, |
| upper_constant_limit); |
| new_limit->InsertBefore(pre_header->end()); |
| limit = new_limit; |
| } |
| |
| // If necessary, redefine the limit in the preheader. |
| if (limit->IsInteger32Constant() && |
| limit->block() != pre_header && |
| !limit->block()->Dominates(pre_header)) { |
| HConstant* new_limit = HConstant::New(zone, context, |
| limit->GetInteger32Constant()); |
| new_limit->InsertBefore(pre_header->end()); |
| limit = new_limit; |
| } |
| |
| // Do the hoisting. |
| HBoundsCheck* hoisted_check = HBoundsCheck::New( |
| zone, context, limit, check->check()->length()); |
| hoisted_check->InsertBefore(pre_header->end()); |
| hoisted_check->set_allow_equality(true); |
| hoisted_check->block()->graph()->isolate()->counters()-> |
| bounds_checks_hoisted()->Increment(); |
| } |
| |
| void CollectInductionVariableData(HBasicBlock* bb) { |
| bool additional_limit = false; |
| |
| for (int i = 0; i < bb->phis()->length(); i++) { |
| HPhi* phi = bb->phis()->at(i); |
| phi->DetectInductionVariable(); |
| } |
| |
| additional_limit = InductionVariableData::ComputeInductionVariableLimit( |
| bb, at(bb)->additional_limit()); |
| |
| if (additional_limit) { |
| at(bb)->additional_limit()->updated_variable-> |
| UpdateAdditionalLimit(at(bb)->additional_limit()); |
| } |
| |
| for (HInstruction* i = bb->first(); i != NULL; i = i->next()) { |
| if (!i->IsBoundsCheck()) continue; |
| HBoundsCheck* check = HBoundsCheck::cast(i); |
| InductionVariableData::BitwiseDecompositionResult decomposition; |
| InductionVariableData::DecomposeBitwise(check->index(), &decomposition); |
| if (!decomposition.base->IsPhi()) continue; |
| HPhi* phi = HPhi::cast(decomposition.base); |
| |
| if (!phi->IsInductionVariable()) continue; |
| InductionVariableData* data = phi->induction_variable_data(); |
| |
| // For now ignore loops decrementing the index. |
| if (data->increment() <= 0) continue; |
| if (!data->LowerLimitIsNonNegativeConstant()) continue; |
| |
| // TODO(mmassi): skip OSR values for check->length(). |
| if (check->length() == data->limit() || |
| check->length() == data->additional_upper_limit()) { |
| check->block()->graph()->isolate()->counters()-> |
| bounds_checks_eliminated()->Increment(); |
| check->set_skip_check(); |
| continue; |
| } |
| |
| if (!phi->IsLimitedInductionVariable()) continue; |
| |
| int32_t limit = data->ComputeUpperLimit(decomposition.and_mask, |
| decomposition.or_mask); |
| phi->induction_variable_data()->AddCheck(check, limit); |
| } |
| |
| for (int i = 0; i < bb->dominated_blocks()->length(); i++) { |
| CollectInductionVariableData(bb->dominated_blocks()->at(i)); |
| } |
| |
| if (additional_limit) { |
| at(bb->block_id())->additional_limit()->updated_variable-> |
| UpdateAdditionalLimit(at(bb->block_id())->additional_limit()); |
| } |
| } |
| |
| void EliminateRedundantBoundsChecks(HBasicBlock* bb) { |
| for (int i = 0; i < bb->phis()->length(); i++) { |
| HPhi* phi = bb->phis()->at(i); |
| if (!phi->IsLimitedInductionVariable()) continue; |
| |
| InductionVariableData* induction_data = phi->induction_variable_data(); |
| InductionVariableData::ChecksRelatedToLength* current_length_group = |
| induction_data->checks(); |
| while (current_length_group != NULL) { |
| current_length_group->CloseCurrentBlock(); |
| InductionVariableData::InductionVariableCheck* current_base_check = |
| current_length_group->checks(); |
| InitializeLoop(induction_data); |
| |
| while (current_base_check != NULL) { |
| ProcessRelatedChecks(current_base_check, induction_data); |
| while (current_base_check != NULL && |
| current_base_check->processed()) { |
| current_base_check = current_base_check->next(); |
| } |
| } |
| |
| current_length_group = current_length_group->next(); |
| } |
| } |
| } |
| |
| private: |
| HGraph* graph_; |
| HBasicBlock* loop_header_; |
| ZoneList<Element> elements_; |
| }; |
| |
| |
| void HBoundsCheckHoistingPhase::HoistRedundantBoundsChecks() { |
| InductionVariableBlocksTable table(graph()); |
| table.CollectInductionVariableData(graph()->entry_block()); |
| for (int i = 0; i < graph()->blocks()->length(); i++) { |
| table.EliminateRedundantBoundsChecks(graph()->blocks()->at(i)); |
| } |
| } |
| |
| } } // namespace v8::internal |
| |