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

src/hydrogen-bounds-check-removal.cc

+// 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.

[titzer, 2013/07/18 12:22:58]

These comments are probably better located on their respective methods.

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

Done.

+ * 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();
+      current_successor_ = kNoBlock;
+      backtrack_to_ = kNoBlock;
+      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;
+    }
+
+    void ClearIterationData() {
+      current_successor_ = kNoBlock;
+      backtrack_to_ = kNoBlock;
+    }
+
+    int ComputeNextBlock(int from_block) {
+      if (current_successor_ == kNoBlock) {
+        backtrack_to_ = from_block;
+      }
+      current_successor_++;
+      if (CurrentSuccessorBlock() != kNoBlock) {
+        return CurrentSuccessorBlock();
+      } else {
+        return backtrack_to_;
+      }
+    }
+
+    int CurrentSuccessorBlock() {
+      if (current_successor_ < block()->end()->SuccessorCount()) {
+        return block()->end()->SuccessorAt(current_successor_)->block_id();
+      } else {
+        return kNoBlock;
+      }
+    }
+
+
+    static const int kIsProcessed = 0;
+    bool IsProcessed() {
+      return current_successor_ == kIsProcessed;
+    }
+    void FlagAsProcessed() {
+      current_successor_ = kIsProcessed;
+    }
+    bool CheckLoopPathsRecursively(InductionVariableBlocksTable* table,
+                                   bool* unsafe) {

[titzer, 2013/07/18 12:22:58]

This is much more readable, good. I think we can do this iteratively (and more
cleanly) using an iterator. Essentially, the iterator would yield one block at a
time, and would have its own internal stack to keep track of the DFS. As we
discussed in person, I don't think that intertwining the state needed to
maintain the traversal within the InductionVariableBlocksTable is readable, and
I think the iterator is the solution.

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

We are going towards a solution where we iterate the dominator tree (or anyway
test dominance relations).

+      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()) {
+          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();
+  }
+
+  void ClearIterationData() {
+    ASSERT(loop_header() != NULL);
+    HLoopInformation* loop = loop_header()->loop_information();
+    for (int i = 0; i < loop->blocks()->length(); i++) {
+      at(loop->blocks()->at(i)->block_id())->ClearIterationData();
+    }
+  }
+
+  /*
+   * 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 true if there are no paths that perform an iteration
+   * (loop back to the header) without meeting a check.
+   * "unsafe" is set if early exit paths are found.
+   */
+  bool LoopPathsAreCheckedIteratively(bool* unsafe) {

[titzer, 2013/07/18 12:22:58]

When you convert this method to use an iterator, please don't pass in a bool*
for unsafe, but instead you can return one of 3 values.

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

Done.

+    *unsafe = false;
+    int previous_block = Element::kNoBlock;
+    int current_block = loop_header()->block_id();
+    while (current_block != Element::kNoBlock) {
+      Element* current_element = at(current_block);
+      int next_block = Element::kNoBlock;
+
+      if (!current_element->is_in_loop()) {
+        if (!current_element->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;
+        }
+        next_block = previous_block;
+      } else if (current_element->is_start() &&
+                 previous_block != Element::kNoBlock &&
+                 previous_block != current_element->CurrentSuccessorBlock()) {
+        // 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;
+      } else if (current_element->has_check()) {
+        // We found a check so this path is safe and we can backtrack.
+        next_block = previous_block;
+      } else {
+        // No special condition, just find the next block in the traversal.
+        next_block = current_element->ComputeNextBlock(previous_block);
+      }
+
+      previous_block = current_block;
+      current_block = next_block;
+    }
+    return true;
+  }
+
+  bool LoopPathsAreCheckedRecursively(bool* unsafe) {
+    return at(loop_header()->block_id())->CheckLoopPathsRecursively(
+        this, unsafe);
+  }
+
+  bool LoopPathsAreChecked(bool* unsafe) {
+    // return LoopPathsAreCheckedIteratively(unsafe);
+    return LoopPathsAreCheckedRecursively(unsafe);
+  }
+
+
+  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();
+    ClearIterationData();
+    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.
+    bool unsafe;
+    bool failure = !LoopPathsAreChecked(&unsafe);

[titzer, 2013/07/18 12:22:58]

If this method just returns a value, then you don't need this weird condition
and pointer.

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

Done.

+    if (failure || (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;
+      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:
+  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
+