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;
+}
+
+/*
+ * This function tries to match the following patterns (and all the relevant
+ * variants related to |, & and + being commutative):
+ * base | or_mask
+ * base & and_mask
+ * (base + constant_offset) & and_mask
+ * (base - constant_offset) & and_mask
+ */
+void InductionVariableData::DecomposeBitwise(
+    HValue* value,
+    BitwiseDecompositionResult* result) {
+  HValue* current = IgnoreOsrValue(value);
+  bool has_offset = false;
+  result->base = value;

[titzer, 2013/07/10 16:34:18]

Thanks for the comment; now that I understand the patterns you would like to
match, I don't think you even need a recursive method. You can first just try to
match the outer |/& operation, and if it succeeds, then try to match the inner
+/- on the non-constant side, and if it fails, try to match the +/- on the whole
thing. It would be far more clear than a loop that does not loop.

[Massi, 2013/07/11 11:15:22]

Done.

+
+  if (!current->representation().IsInteger32()) return;
+
+  while (true) {
+    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);
+
+  set_added_constant(new(index_base->block()->graph()->zone()) HConstant(
+      mask, index_base->representation()));
+  if (added_index() != NULL) {
+    added_constant()->InsertBefore(added_index());
+  } else {
+    added_constant()->InsertBefore(first_check_in_block());
+  }
+
+  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();
+    new_index->AssumeRepresentation(Representation::Integer32());
+    set_added_index(HBitwise::cast(new_index));
+    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;
+  InductionVariableData::DecomposeBitwise(check->index(), &decomposition);
+
+  if (first_check_in_block() == NULL ||
+      first_check_in_block()->block() != check->block()) {
+    CloseCurrentBlock();
+
+    first_check_in_block_ = check;
+    set_added_index(NULL);
+    set_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;
+  }
+}
+
+
+/*
+ * This method detects if phi is an induction variable, with phi_operand as
+ * its "incremented" value (the other operand would be the "base" value).
+ *
+ * It cheks is phi_operand has the form "phi + constant".
+ * If yes, the constant is the increment that the induction variable gets at
+ * every loop iteration.
+ * Otherwise it returns 0.
+ */
+int32_t InductionVariableData::ComputeIncrement(HPhi* phi,
+                                                HValue* phi_operand) {
+  if (!phi_operand->representation().IsInteger32()) return 0;
+
+  if (phi_operand->IsAdd()) {
+    HAdd* operation = HAdd::cast(phi_operand);
+    if (operation->left() == phi &&
+        operation->right()->IsInteger32Constant()) {
+      return operation->right()->GetInteger32Constant();
+    } else if (operation->right() == phi &&
+               operation->left()->IsInteger32Constant()) {
+      return operation->left()->GetInteger32Constant();
+    }
+  } else if (phi_operand->IsSub()) {
+    HSub* operation = HSub::cast(phi_operand);
+    if (operation->left() == phi &&
+        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) {

[titzer, 2013/07/10 16:34:18]

With the name change I see now more clearly what you meant. I actually think you
want to compute whether a given {InductionVariable, Token, limit} is false
leading out of a loop, since that is what is interesting below?

In other words, I am not sure if breaking this operation out into its own method
is worthwhile.

[Massi, 2013/07/11 11:15:22]

Inlined it into CheckIfBranchIsLoopGuard.

+  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) {

[titzer, 2013/07/10 16:34:18]

This is kind of a strange name for this method. I think it should be inlined
(with a comment) into the second of the two methods which I suggest making the
below method into.

[Massi, 2013/07/11 11:15:22]

After the off line discussion I ended up not inlining it (but it now contains
the code of CheckIfBranchIsLoopGuard).

+  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();

[titzer, 2013/07/10 16:34:18]

This method could benefit from being split up into one that matches the
branching pattern from which we derive information (namely the given block is
entered from a predecessor that has a branch on an induction variable) and a
method that consumes that branching pattern and updates either the induction
variable data or the additional limit.

You could have a little datastructure that represents basically the triple

{InductionVariableData induction_variable, Token token, Instruction limit).

[Massi, 2013/07/11 11:15:22]

Done.

+
+  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) {

[titzer, 2013/07/10 16:34:18]

Please just negate the token above, and don't use an intermediate is_else_branch
boolean variable.

[Massi, 2013/07/11 11:15:22]

Done.

+    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