New array bounds check elimination pass (focused on induction variables and bitwise operations).

src/hydrogen-bounds-check-removal.cc

Index: src/hydrogen-bounds-check-removal.cc
diff --git a/src/hydrogen-bounds-check-removal.cc b/src/hydrogen-bounds-check-removal.cc
new file mode 100644
index 0000000000000000000000000000000000000000..578998d6d8312a6ab620bbcf5695957d4bd3aecf
--- /dev/null
+++ b/src/hydrogen-bounds-check-removal.cc
@@ -0,0 +1,418 @@
+// 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.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.
+ *
+ * InitializeLoop() sets up the table for a given loop.
+ * ClearIterationData() prepares the table for a new check.
+ * LoopPathsAreChecked() explores the loop graph searching for paths that do
+ * not contain a check ahains a given induction variable.
+ * ProcessRelatedChecks() is the "main" method that processes all the checks
+ * related to a given induction variable inside its induction loop.
+ */
+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_;
+    }
+
+    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;
+    }
+
+
+    static const int kIsProcessed = 0;
+    bool IsProcessed() {
+      return current_successor_ == kIsProcessed;
+    }
+    void FlagAsProcessed() {
+      current_successor_ = kIsProcessed;
+    }
+    bool CheckLoopPathsRecursively(InductionVariableBlocksTable* table,
+                                   bool* unsafe) {
+      FlagAsProcessed();
+
+      if (has_check()) {
+        // We found a check so this path is safe and we can backtrack.
+        return true;
+      }
+
+      for (int i = 0; i < block()->end()->SuccessorCount(); i ++) {
+        Element* next = table->at(block()->end()->SuccessorAt(i));
+
+        if (!next->is_in_loop()) {

[titzer, 2013/07/22 13:03:10]

This code is now redundant with CheckLoopPaths(Block*).

[Massi, 2013/07/23 07:57:50]

Done.

+          if (!next->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;
+          }
+          return true;
+        }
+
+        if (next->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 false;
+        }
+
+        // Continue the traversal on the current successor.
+        if (!next->CheckLoopPathsRecursively(table, unsafe)) {
+          // Propagate failure.
+          return false;
+        }
+      }
+
+      // We explored all successors with no failures so this path is ok.
+      return true;
+    }
+
+
+    Element()
+        : block_(NULL), current_successor_(kNoBlock), backtrack_to_(kNoBlock),
+          is_start_(false), is_proper_exit_(false), has_check_(false),
+          additional_limit_() {}
+
+   private:
+    HBasicBlock* block_;
+    int current_successor_;
+    int backtrack_to_;
+    bool is_start_;
+    bool is_proper_exit_;
+    bool is_in_loop_;
+    bool has_check_;
+    InductionVariableLimitUpdate additional_limit_;
+  };
+
+  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();
+  }
+
+  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 PathCheckResult {

[titzer, 2013/07/22 13:03:10]

How about HOISTABLE, OPTIMISTICALLY_HOISTABLE, and NOT_HOISTABLE?

[Massi, 2013/07/23 07:57:50]

Done.

+    OK,
+    UNSAFE,
+    FAILURE
+  };
+
+  /*
+   * 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.
+   */
+  PathCheckResult CheckLoopPaths() {

[titzer, 2013/07/22 13:03:10]

CheckHoistability?

[Massi, 2013/07/23 07:57:50]

Done.

+    return CheckLoopPaths(loop_header());
+  }
+
+  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.
+    PathCheckResult check_result = CheckLoopPaths();
+    if (check_result == FAILURE ||
+        (check_result == UNSAFE && !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()->set_skip_check();
+      current_check = current_check->next();
+    }
+
+    // Choose the appropriate limit.
+    HValue* limit = data->limit();
+    if (has_upper_constant_limit) {
+      HConstant* new_limit = new(pre_header->graph()->zone()) HConstant(
+          upper_constant_limit, length->representation());
+      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 = new(pre_header->graph()->zone()) HConstant(
+          limit->GetInteger32Constant(), length->representation());
+      new_limit->InsertBefore(pre_header->end());
+      limit = new_limit;
+    }
+
+    // Do the hoisting.
+    HBoundsCheck* hoisted_check = new(pre_header->zone()) HBoundsCheck(
+        limit, check->check()->length());
+    hoisted_check->InsertBefore(pre_header->end());
+    hoisted_check->set_allow_equality(true);
+  }
+
+  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;

[titzer, 2013/07/22 13:03:10]

Haven't we already done a whole lot of work to deal with induction variables
that are counting down?

[Massi, 2013/07/23 07:57:50]

It depends what we call "a whole lot of work".
What we do is handle both HAdd and HSub when we detect the induction variable,
and flip the sign of the increment in case of HSub.

And note the "for now" in the comment: I just did not want to complicate the
code further, for now.
Handling decreasing induction would need dealing with a single "base upper
bound" (the induction base), and then trying to see if the lower bound is >= 0.

The complication is that further branches would influence the lower bound but
bit masks would still change the upper bound.

This is slightly different from what we do here (test that the single lower
bound is a non negative constant and deal with the potentially different upper
bounds, both because of masks and additional branches), and for now I decided
not to write that code.

+      if (!data->LowerLimitIsNonNegativeConstant()) continue;
+
+      // TODO(mmassi): skip OSR values for check->length().
+      if (check->length() == data->limit() ||
+          check->length() == data->additional_upper_limit()) {
+        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:
+  PathCheckResult CheckLoopPaths(HBasicBlock* block) {

[titzer, 2013/07/22 13:03:10]

Much improved.

+    ASSERT(at(block)->is_in_loop());
+
+    // We found a check so this block is safe and we can backtrack.
+    if (at(block)->has_check()) {
+      return OK;
+    }
+
+    bool unsafe = false;
+    for (int i = 0; i < block->end()->SuccessorCount(); i ++) {
+      Element* successor = at(block->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 FAILURE;
+      }
+    }
+
+    return unsafe ? UNSAFE : OK;
+  }
+
+  HGraph* graph_;
+  HBasicBlock* loop_header_;
+  ZoneList<Element> elements_;
+};
+
+
+void HGraph::EliminateRedundantBoundsChecksUsingInductionVariables() {
+  InductionVariableBlocksTable table(this);
+  table.CollectInductionVariableData(entry_block());
+  for (int i = 0; i < blocks()->length(); i++) {
+    table.EliminateRedundantBoundsChecks(blocks()->at(i));
+  }
+}
+
+} }  // namespace v8::internal
+