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

src/hydrogen-instructions.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 1015 matching lines @@
   if (context->upper_bound() == length() &&
       context->lower_bound_guarantee() != NULL &&
       context->lower_bound_guarantee() != this &&
       context->lower_bound_guarantee()->block() != block() &&
       offset() < context->offset() &&
       index_can_increase() &&
       context->upper_bound_guarantee() == NULL) {
     offset_ = context->offset();
     SetResponsibilityForRange(DIRECTION_UPPER);
     context->set_upper_bound_guarantee(this);
+    isolate()->counters()->bounds_checks_covered()->Increment();
   } else if (context->upper_bound_guarantee() != NULL &&
              context->upper_bound_guarantee() != this &&
              context->upper_bound_guarantee()->block() != block() &&
              offset() > context->offset() &&
              index_can_decrease() &&
              context->lower_bound_guarantee() == NULL) {
     offset_ = context->offset();
     SetResponsibilityForRange(DIRECTION_LOWER);
     context->set_lower_bound_guarantee(this);
+    isolate()->counters()->bounds_checks_covered()->Increment();
   }
 }
 
 
 void HBoundsCheck::ApplyIndexChange() {
   if (skip_check()) return;
 
   DecompositionResult decomposition;
   bool index_is_decomposable = index()->TryDecompose(&decomposition);
   if (index_is_decomposable) {
@@ skipping 40 matching lines @@
   scale_ = 0;
   responsibility_direction_ = DIRECTION_NONE;
 }
 
 
 void HBoundsCheck::AddInformativeDefinitions() {
   // TODO(mmassi): Executing this code during AddInformativeDefinitions
   // is a hack. Move it to some other HPhase.
   if (FLAG_array_bounds_checks_elimination) {
     if (index()->TryGuaranteeRange(length())) {
-      set_skip_check(true);
+      set_skip_check();
     }
     if (DetectCompoundIndex()) {
       HBoundsCheckBaseIndexInformation* base_index_info =
           new(block()->graph()->zone())
           HBoundsCheckBaseIndexInformation(this);
       base_index_info->InsertAfter(this);
     }
   }
 }
 
@@ skipping 825 matching lines @@
       result = false;
       break;
     }
   }
   ClearFlag(kNumericConstraintEvaluationInProgress);
 
   return result;
 }
 
 
+InductionVariableData* InductionVariableData::ExaminePhi(HPhi* phi) {
+  if (phi->block()->loop_information() == NULL) return NULL;
+  if (phi->OperandCount() != 2) return NULL;
+  int32_t candidate_increment;
+
+  candidate_increment = ComputeIncrement(phi, phi->OperandAt(0));
+  if (candidate_increment != 0) {
+    return new(phi->block()->graph()->zone())
+        InductionVariableData(phi, phi->OperandAt(1), candidate_increment);
+  }
+
+  candidate_increment = ComputeIncrement(phi, phi->OperandAt(1));
+  if (candidate_increment != 0) {
+    return new(phi->block()->graph()->zone())
+        InductionVariableData(phi, phi->OperandAt(0), candidate_increment);
+  }
+
+  return NULL;
+}
+
+
+void InductionVariableData::DecomposeBitwise(
+    HValue* value,
+    BitwiseDecompositionResult* result) {
+  HValue* current = IgnoreOsrValue(value);
+  bool has_offset = false;
+  result->base = value;
+  result->and_mask = 0;
+  result->or_mask = 0;
+  result->context = NULL;
+
+  if (!current->representation().IsInteger32()) return;
+
+  while (true) {

[titzer, 2013/07/02 13:45:06]

I do not understand why this pattern matching is a loop. It can only iterate
from the ADD or SUB cases, both of which check that the masks are both 0--but
that seems redundant because all the other cases return. Then you have a
sentinel to indicate that you have matched an offset with an ADD or SUB in order
to force the OR case to abort.

Basically, I cannot figure which patterns this code matches or is supposed to
match. In most situations pattern matching is best done recursively and I would
advocate strongly to do so here. Also, a comment would help a lot--including a
grammar of which patterns would be matched, for example, would save the reader a
ton of work decoding this.

[Massi, 2013/07/08 11:55:07]

Added a comment.
I still think that having the loop is simpler because to implement it
recursively I'd have to pass along "has_offset" and "current" as additional
arguments, which would mean having an "internal" recursive version of the method
or something similar.

+    if (current->IsAdd()) {
+      if (result->and_mask != 0 || result->or_mask != 0) return;
+      HAdd* operation = HAdd::cast(current);
+      if (operation->right()->IsInteger32Constant()) {
+        has_offset = true;
+        current = operation->left();
+      } else if (operation->left()->IsInteger32Constant()) {
+        has_offset = true;
+        current = operation->right();
+      } else {
+        return;
+      }
+      continue;
+    } else if (current->IsSub()) {
+      if (result->and_mask != 0 || result->or_mask != 0) return;
+      HSub* operation = HSub::cast(current);
+      if (operation->right()->IsInteger32Constant()) {
+        has_offset = true;
+        current = operation->left();
+      } else {
+        return;
+      }
+      continue;
+    } else if (current->IsBitwise()) {
+      HBitwise* operation = HBitwise::cast(current);
+      int32_t* mask = NULL;
+      if (operation->op() == Token::BIT_AND) {
+        mask = &(result->and_mask);
+      } else if (operation->op() == Token::BIT_OR) {
+        if (has_offset) {
+          return;
+        }
+        mask = &(result->or_mask);
+      } else {
+        return;
+      }
+      if (operation->right()->IsInteger32Constant()) {
+        *mask = operation->right()->GetInteger32Constant();
+        current = operation->left();
+      } else if (operation->left()->IsInteger32Constant()) {
+        *mask = operation->left()->GetInteger32Constant();
+        current = operation->right();
+      }
+      result->context = operation->context();
+      result->base = current;
+      return;
+    } else {
+      return;
+    }
+  }
+
+  return;
+}
+
+
+void InductionVariableData::AddCheck(HBoundsCheck* check,
+                                     int32_t upper_limit) {
+  ASSERT(limit_validity() != NULL);
+  if (limit_validity() != check->block() &&
+      !limit_validity()->Dominates(check->block())) return;
+  if (!phi()->block()->current_loop()->IsNestedInThisLoop(
+      check->block()->current_loop())) return;
+
+  ChecksRelatedToLength* length_checks = checks();
+  while (length_checks != NULL) {
+    if (length_checks->length() == check->length()) break;
+    length_checks = length_checks->next();
+  }
+  if (length_checks == NULL) {
+    length_checks = new(check->block()->zone())
+        ChecksRelatedToLength(check->length(), checks());
+    checks_ = length_checks;
+  }
+
+  length_checks->AddCheck(check, upper_limit);
+}
+
+void InductionVariableData::ChecksRelatedToLength::CloseCurrentBlock() {
+  if (checks() != NULL) {
+    InductionVariableCheck* c = checks();
+    HBasicBlock* current_block = c->check()->block();
+    while (c != NULL && c->check()->block() == current_block) {
+      c->set_upper_limit(current_upper_limit_);
+      c = c->next();
+    }
+  }
+}
+
+
+void InductionVariableData::ChecksRelatedToLength::UseNewIndexInCurrentBlock(
+    Token::Value token,
+    int32_t mask,
+    HValue* index_base,
+    HValue* context) {
+  ASSERT(first_check_in_block() != NULL);
+  HValue* previous_index = first_check_in_block()->index();
+  ASSERT(context != NULL);
+
+  added_constant_ = new(index_base->block()->graph()->zone()) HConstant(
+      mask, index_base->representation());
+  HInstruction* constant_insertion_point;
+  if (added_index() != NULL) {
+    constant_insertion_point = added_index();
+  } else {
+    constant_insertion_point = first_check_in_block();
+  }
+  added_constant()->InsertBefore(constant_insertion_point);

[titzer, 2013/07/02 13:45:06]

Just move this code up into the if and save two lines. You will also then have a
redundant branch on added_index != NULL which you can then fold together.

[Massi, 2013/07/08 11:55:07]

I tried that, with the ternary ?:, but added_index() and first_check_in_block()
have different types, therefore writing the ternary expression would have
required casts... I just did not find the expression with those casts readable
at all :-(
But yes, I can invoke "InsertBefore" in each if branch :-)

+
+  if (added_index() == NULL) {
+    first_check_in_block()->ReplaceAllUsesWith(first_check_in_block()->index());
+    HInstruction* new_index =  HBitwise::New(
+        index_base->block()->graph()->zone(),
+        token, context, index_base, added_constant());
+    ASSERT(new_index->IsBitwise());
+    new_index->ClearAllSideEffects();

[titzer, 2013/07/02 13:45:06]

What side effects might the new index have that you are clearing? Some weird
JS-iness?

[Massi, 2013/07/08 11:55:07]

IIRC calling "toNumber()", which in our case is guaranteed not to happen.

+    new_index->AssumeRepresentation(Representation::Integer32());
+    added_index_ = HBitwise::cast(new_index);

[titzer, 2013/07/02 13:45:06]

There are several assignments of private variables directly and then also getter
uses. Suggest just going with a direct private access for consistency.

[Massi, 2013/07/08 11:55:07]

The logic was to use the private variable for writing and the getter for
reading, I added a setter for writing.

+    added_index()->InsertBefore(first_check_in_block());
+  }
+  ASSERT(added_index()->op() == token);
+
+  added_index()->SetOperandAt(1, index_base);
+  added_index()->SetOperandAt(2, added_constant());
+  first_check_in_block()->SetOperandAt(0, added_index());
+  if (previous_index->UseCount() == 0) {
+    previous_index->DeleteAndReplaceWith(NULL);
+  }
+}
+
+void InductionVariableData::ChecksRelatedToLength::AddCheck(
+    HBoundsCheck* check,
+    int32_t upper_limit) {
+  BitwiseDecompositionResult decomposition;

[titzer, 2013/07/02 13:45:06]

Probably better to initialize this struct at the declaration site (either with a
constructor or explicitly here), rather than in the decompose method.

[Massi, 2013/07/08 11:55:07]

Added parameterless constructor, even if I still think that it is
InductionVariableData::DecomposeBitwise that produces the result therefore it
should be the one with the responsibility to initialize it.

+  InductionVariableData::DecomposeBitwise(check->index(), &decomposition);
+
+  if (first_check_in_block() == NULL ||
+      first_check_in_block()->block() != check->block()) {
+    CloseCurrentBlock();
+
+    first_check_in_block_ = check;
+    added_index_ = NULL;
+    added_constant_ = NULL;
+    current_and_mask_in_block_ = decomposition.and_mask;
+    current_or_mask_in_block_ = decomposition.or_mask;
+    current_upper_limit_ = upper_limit;
+
+    InductionVariableCheck* new_check = new(check->block()->graph()->zone())
+        InductionVariableCheck(check, checks_, upper_limit);
+    checks_ = new_check;
+    return;
+  }
+
+  if (upper_limit > current_upper_limit()) {
+    current_upper_limit_ = upper_limit;
+  }
+
+  if (decomposition.and_mask != 0 &&
+      current_or_mask_in_block() == 0) {
+    if (current_and_mask_in_block() == 0 ||
+        decomposition.and_mask > current_and_mask_in_block()) {
+      UseNewIndexInCurrentBlock(Token::BIT_AND,
+                                decomposition.and_mask,
+                                decomposition.base,
+                                decomposition.context);
+      current_and_mask_in_block_ = decomposition.and_mask;
+    }
+    check->set_skip_check();
+  }
+  if (current_and_mask_in_block() == 0) {
+    if (decomposition.or_mask > current_or_mask_in_block()) {
+      UseNewIndexInCurrentBlock(Token::BIT_OR,
+                                decomposition.or_mask,
+                                decomposition.base,
+                                decomposition.context);
+      current_or_mask_in_block_ = decomposition.or_mask;
+    }
+    check->set_skip_check();
+  }
+
+  if (!check->skip_check()) {
+    InductionVariableCheck* new_check = new(check->block()->graph()->zone())
+        InductionVariableCheck(check, checks_, upper_limit);
+    checks_ = new_check;
+  }
+}
+
+
+int32_t InductionVariableData::ComputeIncrement(HPhi* phi,

[titzer, 2013/07/02 13:45:06]

Comments documenting this method.

[Massi, 2013/07/08 11:55:07]

Done.

+                                                HValue* phi_operand) {
+  if (!phi_operand->representation().IsInteger32()) return 0;
+
+  if (phi_operand->IsAdd()) {
+    HAdd* operation = HAdd::cast(phi_operand);
+    if (operation->left() == phi) {

[titzer, 2013/07/02 13:45:06]

You can further shorten these branches with &&.

[Massi, 2013/07/08 11:55:07]

Done.

+      if (operation->right()->IsInteger32Constant()) {
+        return operation->right()->GetInteger32Constant();
+      }
+    } else if (operation->right() == phi) {
+      if (operation->left()->IsInteger32Constant()) {
+        return operation->left()->GetInteger32Constant();
+      }
+    }
+  } else if (phi_operand->IsSub()) {
+    HSub* operation = HSub::cast(phi_operand);
+    if (operation->left() == phi) {
+      if (operation->right()->IsInteger32Constant()) {
+        return -operation->right()->GetInteger32Constant();
+      }
+    }
+  }
+
+  return 0;
+}
+
+
+HValue* InductionVariableData::IgnoreOsrValue(HValue* v) {
+  if (!v->IsPhi()) return v;
+  HPhi* phi = HPhi::cast(v);
+  if (phi->OperandCount() != 2) return v;
+  if (phi->OperandAt(0)->block()->is_osr_entry()) {
+    return phi->OperandAt(1);
+  } else if (phi->OperandAt(1)->block()->is_osr_entry()) {
+    return phi->OperandAt(0);
+  } else {
+    return v;
+  }
+}
+
+
+InductionVariableData* InductionVariableData::GetInductionVariableData(
+    HValue* v) {
+  v = IgnoreOsrValue(v);
+  if (v->IsPhi()) {
+    return HPhi::cast(v)->induction_variable_data();
+  }
+  return NULL;
+}
+
+
+/*
+ * Check if a comparison token can represent a branch that keeps the control
+ * flow inside a loop (in other words, the branch where the increment is still
+ * applied to the induction variable).
+ * If this is true, then the condition associated with the branch can be the
+ * induction variable limit for the loop.
+ */
+bool InductionVariableData::TokenCanRepresentLoopGuard(Token::Value token) {
+  if (increment() > 0 && (token == Token::GT || token == Token::GTE)) {
+    return false;
+  }
+  if (increment() < 0 && (token == Token::GT || token == Token::GTE)) {
+    return false;
+  }
+  if (Token::IsInequalityOp(token) && increment() != 1 && increment() != -1) {
+    return false;
+  }
+  return true;
+}
+
+
+bool InductionVariableData::CheckIfBranchIsLoopGuard(HBasicBlock* in_branch,
+                                                     HBasicBlock* out_branch) {
+  return phi()->block()->current_loop()->IsNestedInThisLoop(
+        in_branch->current_loop()) &&
+      !phi()->block()->current_loop()->IsNestedInThisLoop(
+        out_branch->current_loop());
+}
+
+
+bool InductionVariableData::ComputeInductionVariableLimit(
+    HBasicBlock* block,
+    InductionVariableLimitUpdate* additional_limit) {
+  if (block->predecessors()->length() != 1) return false;
+  HBasicBlock* predecessor = block->predecessors()->at(0);
+  HInstruction* end = predecessor->last();
+
+  if (!end->IsCompareIDAndBranch()) return false;
+  HCompareIDAndBranch* branch = HCompareIDAndBranch::cast(end);
+
+  Token::Value token = branch->token();
+  if (!Token::IsArithmeticCompareOp(token)) return false;
+
+  bool is_else_branch;
+  HBasicBlock* other_target;
+  if (block == branch->SuccessorAt(0)) {
+    is_else_branch = false;
+    other_target = branch->SuccessorAt(1);
+  } else {
+    is_else_branch = true;
+    other_target = branch->SuccessorAt(0);
+    ASSERT(block == branch->SuccessorAt(1));
+  }
+
+  if (is_else_branch) {
+    token = Token::NegateCompareOp(token);
+  }
+  bool limit_included = (Token::IsEqualityOp(token) ||
+                         token == Token::GTE || token == Token::LTE);
+
+  InductionVariableData* data;
+
+  data = GetInductionVariableData(branch->left());
+  Token::Value actual_token = token;
+  HValue* limit = branch->right();
+  if (data == NULL) {
+    data = GetInductionVariableData(branch->right());
+    actual_token = Token::ReverseCompareOp(token);
+    limit = branch->left();
+  }
+
+  if (data != NULL) {
+    if (data->TokenCanRepresentLoopGuard(actual_token) &&
+        data->CheckIfBranchIsLoopGuard(block, other_target)) {
+      data->limit_ = limit;
+      data->limit_included_ = limit_included;
+      data->limit_validity_ = block;
+      data->induction_exit_block_ = predecessor;
+      data->induction_exit_target_ = other_target;
+      return false;
+    } else {
+      additional_limit->updated_variable = data;
+      additional_limit->limit = limit;
+      additional_limit->limit_is_upper = (actual_token == Token::LTE ||
+                                          actual_token == Token::LT ||
+                                          actual_token == Token::NE);
+      additional_limit->limit_is_included = limit_included;
+      return true;
+    }
+  }
+
+  return false;
+}
+
+
 Range* HMathMinMax::InferRange(Zone* zone) {
   if (representation().IsInteger32()) {
     Range* a = left()->range();
     Range* b = right()->range();
     Range* res = a->Copy(zone);
     if (operation_ == kMathMax) {
       res->CombinedMax(b);
     } else {
       ASSERT(operation_ == kMathMin);
       res->CombinedMin(b);
@@ skipping 1905 matching lines @@
     case kBackingStore:
       if (!name_.is_null()) stream->Add(*String::cast(*name_)->ToCString());
       stream->Add("[backing-store]");
       break;
   }
 
   stream->Add("@%d", offset());
 }
 
 } }  // namespace v8::internal