Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1743)

Unified Diff: src/crankshaft/hydrogen-bch.cc

Issue 1823623002: [crankshaft] Delete unused Hydrogen-BCH code (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: Created 4 years, 9 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « src/crankshaft/hydrogen-bch.h ('k') | src/crankshaft/hydrogen-instructions.h » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/crankshaft/hydrogen-bch.cc
diff --git a/src/crankshaft/hydrogen-bch.cc b/src/crankshaft/hydrogen-bch.cc
deleted file mode 100644
index 060e0bcdabb488c6181ea72906a6f722040235b0..0000000000000000000000000000000000000000
--- a/src/crankshaft/hydrogen-bch.cc
+++ /dev/null
@@ -1,379 +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/crankshaft/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) {
- DCHECK(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() {
- DCHECK(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() const { return graph_; }
- Counters* counters() const { return graph()->isolate()->counters(); }
- HBasicBlock* loop_header() const { return loop_header_; }
- Element* at(int index) const { return &(elements_.at(index)); }
- Element* at(HBasicBlock* block) const { 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());
- DCHECK(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;
- int32_t upper_constant_limit =
- check->HasUpperLimit() ? check->upper_limit() : 0;
- for (InductionVariableData::InductionVariableCheck* current_check = check;
- current_check != NULL;
- current_check = current_check->next()) {
- has_upper_constant_limit =
- has_upper_constant_limit && current_check->HasUpperLimit() &&
- current_check->upper_limit() == upper_constant_limit;
- counters()->bounds_checks_eliminated()->Increment();
- current_check->check()->set_skip_check();
- }
-
- // 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(graph()->isolate(), 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(graph()->isolate(), zone, context,
- limit->GetInteger32Constant());
- new_limit->InsertBefore(pre_header->end());
- limit = new_limit;
- }
-
- // Do the hoisting.
- HBoundsCheck* hoisted_check = HBoundsCheck::New(
- graph()->isolate(), zone, context, limit, check->check()->length());
- hoisted_check->InsertBefore(pre_header->end());
- hoisted_check->set_allow_equality(true);
- 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()) {
- 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 internal
-} // namespace v8
« no previous file with comments | « src/crankshaft/hydrogen-bch.h ('k') | src/crankshaft/hydrogen-instructions.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698