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

src/hydrogen.cc

 // Copyright 2012 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
@@ skipping 4233 matching lines @@
                                      new_offset);
         if (!result) return false;
         lower_check_->ReplaceAllUsesWith(lower_check_->index());
         lower_check_->SetOperandAt(0, added_lower_index_);
       }
     } else {
       ASSERT(false);
     }
 
     if (!keep_new_check) {
+      BasicBlock()->graph()->isolate()->counters()->
+          bounds_checks_covered()->Increment();
       new_check->DeleteAndReplaceWith(new_check->ActualValue());
     }
 
     return true;
   }
 
   void RemoveZeroOperations() {
     RemoveZeroAdd(&added_lower_index_, &added_lower_offset_);
     RemoveZeroAdd(&added_upper_index_, &added_upper_offset_);
   }
@@ skipping 102 matching lines @@
   void Delete(BoundsCheckKey* key) {
     Remove(key, key->Hash());
   }
 
   explicit BoundsCheckTable(Zone* zone)
       : ZoneHashMap(BoundsCheckKeyMatch, ZoneHashMap::kDefaultHashMapCapacity,
                     ZoneAllocationPolicy(zone)) { }
 };
 
 
+class InductionVariableBlocksTable BASE_EMBEDDED {

[titzer, 2013/06/24 14:03:30]

Highly recommend moving this class and related functionality into a new file
specifically for doing bounds check elimination.

[Massi, 2013/07/01 13:10:49]

Done.

+ public:
+  class Element {
+   public:
+    static const int kNoBlock = -1;
+
+    HBasicBlock* block() { return block_; }
+    void set_block(HBasicBlock* block) { block_ = block; }
+    int current_successor() { return current_successor_; }
+    int backtrack_to() { return backtrack_to_; }
+    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());
+      has_check_ = false;
+    }
+
+    void ClearIterationData() {
+      current_successor_ = kNoBlock;
+      backtrack_to_ = kNoBlock;
+    }
+
+    int CurrentSuccessorBlock() {
+      if (current_successor_ < block()->end()->SuccessorCount()) {
+        return block()->end()->SuccessorAt(current_successor_)->block_id();
+      } else {
+        return kNoBlock;
+      }
+    }
+
+    int PerformStep(int from_block, bool* failure, bool* unsafe) {
+      if (!is_in_loop()) {
+        if (!is_proper_exit()) {
+          *unsafe = true;
+        }
+        return from_block;
+      }
+
+      if (is_start() &&
+          from_block != kNoBlock &&
+          from_block != CurrentSuccessorBlock()) {
+        *failure = true;
+        return from_block;
+      }
+
+      if (has_check()) {
+        return from_block;
+      }
+
+      if (current_successor_ == kNoBlock) {
+        backtrack_to_ = from_block;
+      }
+      current_successor_++;
+
+      if (CurrentSuccessorBlock() != kNoBlock) {
+        return CurrentSuccessorBlock();
+      } else {
+        return backtrack_to();
+      }
+    }
+
+    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 add_check_at(int index) {
+    at(index)->set_has_check();
+  }
+  void add_check_at(HBasicBlock* block) {
+    add_check_at(block->block_id());
+  }
+
+  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();
+    }
+  }
+
+  bool LoopPathsAreChecked(bool* unsafe) {
+    bool failure = false;
+    *unsafe = false;
+    int previous_block = Element::kNoBlock;
+    int current_block = loop_header()->block_id();
+    while (current_block != Element::kNoBlock) {
+      int next_block = at(current_block)->PerformStep(previous_block,
+                                                      &failure, unsafe);
+      previous_block = current_block;
+      current_block = next_block;
+      if (failure) return false;
+    }
+    return true;
+  }
+
+  void AddCheck(HBoundsCheck* check) {
+    at(check->block()->block_id())->set_has_check();
+  }
+
+  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);
+    }
+  }
+
+  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);
+    if (!data->limit()->IsInteger32Constant()) {
+      HBasicBlock* limit_block = data->limit()->block();
+      if (limit_block != pre_header &&
+          !limit_block->Dominates(pre_header)) {
+        return;
+      }
+    }
+    if (!(data->limit()->representation().Equals(
+            length->representation()) ||
+        data->limit()->IsInteger32Constant())) {
+      return;
+    }
+    if (check->check()->length()->block() != pre_header &&
+        !check->check()->length()->block()->Dominates(pre_header)) {
+      return;
+    }
+
+    for (InductionVariableData::InductionVariableCheck* current_check = check;
+         current_check != NULL;
+         current_check = current_check->next()) {
+      if (current_check->check()->length() != length) continue;
+
+      add_check_at(current_check->check()->block());
+      current_check->set_processed();
+    }
+
+    bool unsafe;
+    bool failure = !LoopPathsAreChecked(&unsafe);
+
+    if (failure || (unsafe && !graph()->use_optimistic_licm())) {
+      return;
+    }
+
+    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();
+    }
+
+    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 (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;
+    }
+    HBoundsCheck* hoisted_check = new(pre_header->zone()) HBoundsCheck(
+        limit, check->check()->length());
+    hoisted_check->InsertBefore(pre_header->end());
+    hoisted_check->set_allow_equality(true);
+  }
+
+ private:
+  HGraph* graph_;
+  HBasicBlock* loop_header_;
+  ZoneList<Element> elements_;
+};
+
+
+void HGraph::CollectInductionVariableData(
+    HBasicBlock* bb,
+    InductionVariableBlocksTable* table) {
+  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, table->at(bb)->additional_limit());
+
+  if (additional_limit) {
+    table->at(bb)->additional_limit()->updated_variable->
+        UpdateAdditionalLimit(table->at(bb)->additional_limit());
+  }
+
+  for (HInstruction* i = bb->first(); i != NULL; i = i->next()) {
+    if (!i->IsBoundsCheck()) continue;
+    HBoundsCheck* check = HBoundsCheck::cast(i);
+    int32_t and_mask;
+    int32_t or_mask;
+    HValue* context;
+    HValue* base_index = InductionVariableData::DecomposeBitwise(
+        check->index(), &and_mask, &or_mask, &context);
+    if (!base_index->IsPhi()) continue;
+    HPhi* phi = HPhi::cast(base_index);
+
+    if (!phi->IsInductionVariable()) continue;
+    InductionVariableData* data = phi->induction_variable_data();
+
+    // For now ignore loops decrementing the index.
+    if (data->increment() <= 0) continue;
+    if (!data->lower_limit_is_non_negative_constant()) 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(and_mask, 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), table);
+  }
+
+  if (additional_limit) {
+    table->at(bb->block_id())->additional_limit()->updated_variable->
+        UpdateAdditionalLimit(table->at(bb->block_id())->additional_limit());
+  }
+}
+
+
+void HGraph::EliminateRedundantBoundsChecksUsingInductionVariables(
+    HBasicBlock* bb,
+    InductionVariableBlocksTable* table) {
+  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();
+      table->InitializeLoop(induction_data);
+
+      while (current_base_check != NULL) {
+        table->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();
+    }
+  }
+}
+
+
+void HGraph::EliminateRedundantBoundsChecksUsingInductionVariables() {
+  InductionVariableBlocksTable table(this);
+  CollectInductionVariableData(entry_block(), &table);
+  for (int i = 0; i < blocks()->length(); i++) {
+    EliminateRedundantBoundsChecksUsingInductionVariables(blocks()->at(i),
+                                                          &table);
+  }
+}
+
+
 // 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 HGraph::EliminateRedundantBoundsChecks(HBasicBlock* bb,
                                             BoundsCheckTable* table) {
   BoundsCheckBbData* bb_data_list = NULL;
 
   for (HInstruction* i = bb->first(); i != NULL; i = i->next()) {
@@ skipping 55 matching lines @@
       table->Delete(data->Key());
     }
   }
 }
 
 
 void HGraph::EliminateRedundantBoundsChecks() {
   HPhase phase("H_Eliminate bounds checks", this);
   BoundsCheckTable checks_table(zone());
   EliminateRedundantBoundsChecks(entry_block(), &checks_table);
+    if (FLAG_abcd_ivars) {
+      EliminateRedundantBoundsChecksUsingInductionVariables();
+    }
 }
 
 
 static void DehoistArrayIndex(ArrayInstructionInterface* array_operation) {
   HValue* index = array_operation->GetKey()->ActualValue();
   if (!index->representation().IsSmiOrInteger32()) return;
 
   HConstant* constant;
   HValue* subexpression;
   int32_t sign;
@@ skipping 7192 matching lines @@
     }
   }
 
 #ifdef DEBUG
   if (graph_ != NULL) graph_->Verify(false);  // No full verify.
   if (allocator_ != NULL) allocator_->Verify();
 #endif
 }
 
 } }  // namespace v8::internal