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 | constant_or_mask
+ * base & constant_and_mask
+ * (base + constant_offset) & constant_and_mask
+ * (base - constant_offset) & constant_and_mask

[titzer, 2013/07/11 16:39:10]

Why do we not also want to match "base + constant_offset" and "base -
constant_offset"?

[Massi, 2013/07/12 08:20:24]

Because collapsing those patterns is the job of the other array bounds
elimination pass.
Of course we could also handle hoisting of "base + constant" patterns but I did
not think that the added complexity was worth it (at that point we would end up
with the "all encompassing" idef based approach).

+ */
+void InductionVariableData::DecomposeBitwise(
+    HValue* value,
+    BitwiseDecompositionResult* result) {
+  HValue* base = IgnoreOsrValue(value);
+  result->base = value;
+  int32_t* mask_location = NULL;
+  int32_t mask = 0;
+
+  if (!base->representation().IsInteger32()) return;
+
+  if (base->IsBitwise()) {
+    bool allow_offset = false;
+
+    HBitwise* bitwise = HBitwise::cast(base);
+    if (bitwise->op() == Token::BIT_AND) {
+      mask_location = &(result->and_mask);
+      allow_offset = true;
+    } else if (bitwise->op() == Token::BIT_OR) {
+      mask_location = &(result->or_mask);
+    } else {
+      return;
+    }
+    if (bitwise->right()->IsInteger32Constant()) {

[titzer, 2013/07/11 16:39:10]

If you get the mask first, before matching AND or OR, then you don't need
mask_location, and probably also don't need allow_offset.

[Massi, 2013/07/12 08:20:24]

True about mask, but we still want to allow those offsets in the "bitwise and"
case.
To be fair we could allow *anything* in the bitwise and case (the constant
operand is an upper limit anyway) but I did not want to go that far.

+      mask = bitwise->right()->GetInteger32Constant();
+      base = bitwise->left();
+    } else if (bitwise->left()->IsInteger32Constant()) {
+      mask = bitwise->left()->GetInteger32Constant();
+      base = bitwise->right();
+    } else {
+      return;
+    }
+
+    *mask_location = mask;
+    result->context = bitwise->context();
+
+    if (allow_offset) {
+      if (base->IsAdd()) {
+        HAdd* add = HAdd::cast(base);
+        if (add->right()->IsInteger32Constant()) {
+          base = add->left();
+        } else if (add->left()->IsInteger32Constant()) {
+          base = add->right();
+        }
+      } else if (base->IsSub()) {
+        HSub* sub = HSub::cast(base);
+        if (sub->right()->IsInteger32Constant()) {
+          base = sub->left();
+        }
+      }
+    }
+
+    result->base = base;
+  }
+}
+
+
+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 conditional branch to "current_branch" with token "token" is
+ * the branch that keeps the induction loop running (and, conversely, will
+ * terminate it if the "other_branch" is taken).
+ *
+ * Three conditions must be met:
+ * - "current_branch" must be in the induction loop.
+ * - "other_branch" must be out of the induction loop.
+ * - "token" and the induction increment must be "compatible": the token should
+ *   be a condition that keeps the execution inside the loop until the limit is
+ *   reached.
+ */
+bool InductionVariableData::CheckIfBranchIsLoopGuard(
+    Token::Value token,
+    HBasicBlock* current_branch,

[titzer, 2013/07/11 16:39:10]

If I understand this code correctly now, this is the "true" target of a
hypothetical branch comparing the induction variable with "token" against some
limit. If that's true, I suggest "true_target" and "false_target" for the basic
block parameter names.

+    HBasicBlock* other_branch) {
+  if (!phi()->block()->current_loop()->IsNestedInThisLoop(
+      current_branch->current_loop())) {
+    return false;
+  }
+
+  if (phi()->block()->current_loop()->IsNestedInThisLoop(
+      other_branch->current_loop())) {
+    return false;
+  }
+
+  if (increment() > 0 && (token == Token::LT || token == Token::LTE)) {
+    return true;
+  }
+  if (increment() < 0 && (token == Token::GT || token == Token::GTE)) {
+    return true;
+  }
+  if (Token::IsInequalityOp(token) && (increment() == 1 || increment() == -1)) {
+    return true;
+  }
+
+  return false;
+}
+
+
+void InductionVariableData::ComputeLimitFromPredecessorBlock(
+    HBasicBlock* block,
+    LimitFromPredecessorBlock* result) {
+  if (block->predecessors()->length() != 1) return;
+  HBasicBlock* predecessor = block->predecessors()->at(0);
+  HInstruction* end = predecessor->last();
+
+  if (!end->IsCompareIDAndBranch()) return;
+  HCompareIDAndBranch* branch = HCompareIDAndBranch::cast(end);
+
+  Token::Value token = branch->token();
+  if (!Token::IsArithmeticCompareOp(token)) return;
+
+  HBasicBlock* other_target;
+  if (block == branch->SuccessorAt(0)) {
+    other_target = branch->SuccessorAt(1);
+  } else {
+    other_target = branch->SuccessorAt(0);
+    token = Token::NegateCompareOp(token);
+    ASSERT(block == branch->SuccessorAt(1));
+  }
+
+  InductionVariableData* data;
+
+  data = GetInductionVariableData(branch->left());
+  HValue* limit = branch->right();
+  if (data == NULL) {
+    data = GetInductionVariableData(branch->right());
+    token = Token::ReverseCompareOp(token);
+    limit = branch->left();
+  }
+
+  if (data != NULL) {
+    result->variable = data;
+    result->token = token;
+    result->limit = limit;
+    result->other_target = other_target;
+  }
+}
+
+/*
+ * Compute the limit that is imposed on an induction variable when entering
+ * "block" (if any).
+ * If the limit is the "proper" induction limit (the one that makes the loop
+ * terminate when the induction variable reaches it) it is stored directly in
+ * the induction variable data.
+ * Otherwise the limit is written in "additional_limit" and the method
+ * returns true.
+ */
+bool InductionVariableData::ComputeInductionVariableLimit(
+    HBasicBlock* block,
+    InductionVariableLimitUpdate* additional_limit) {
+  LimitFromPredecessorBlock limit;
+  ComputeLimitFromPredecessorBlock(block, &limit);
+  if (!limit.LimitIsValid()) return false;
+
+  if (limit.variable->CheckIfBranchIsLoopGuard(limit.token,
+                                               block,
+                                               limit.other_target)) {
+    limit.variable->limit_ = limit.limit;
+    limit.variable->limit_included_ = limit.LimitIsIncluded();
+    limit.variable->limit_validity_ = block;
+    limit.variable->induction_exit_block_ = block->predecessors()->at(0);
+    limit.variable->induction_exit_target_ = limit.other_target;
+    return false;
+  } else {
+    additional_limit->updated_variable = limit.variable;
+    additional_limit->limit = limit.limit;
+    additional_limit->limit_is_upper = limit.LimitIsUpper();
+    additional_limit->limit_is_included = limit.LimitIsIncluded();
+    return true;
+  }
+}
+
+
 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