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::New(HPhi* phi) {

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

This method really isn't a "new" or constructor method, since it can return
NULL. It needs a more descriptive name.

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

Done (renamed as "ExaminePhi").

+  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;
+}
+
+
+HValue* InductionVariableData::DecomposeBitwise(HValue* value,
+                                                int32_t* and_mask,
+                                                int32_t* or_mask,
+                                                HValue** context) {

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

Returning potentially four different values via pointer is getting a little
awkward here. I think a little data object, either created in the caller or the
callee, would be cleaner.

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

Done.

+  HValue* current = DiscardOsrValue(value);
+  bool has_offset = false;
+  *and_mask = 0;
+  *or_mask = 0;
+  *context = NULL;
+
+  if (!current->representation().IsInteger32()) return value;
+
+  while (true) {
+    if (current->IsAdd()) {
+      if (and_mask != 0 || or_mask != 0) return value;
+      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 value;
+      }
+      continue;
+    } else if (current->IsSub()) {
+      if (and_mask != 0 || or_mask != 0) return value;
+      HSub* operation = HSub::cast(current);
+      if (operation->right()->IsInteger32Constant()) {
+        has_offset = true;
+        current = operation->left();
+      } else {
+        return value;
+      }
+      continue;
+    } else if (current->IsBitwise()) {
+      HBitwise* operation = HBitwise::cast(current);
+      int32_t* mask = NULL;
+      if (operation->op() == Token::BIT_AND) {
+        mask = and_mask;
+      } else if (operation->op() == Token::BIT_OR) {
+        if (has_offset) {
+          return value;
+        }
+        mask = or_mask;
+      } else {
+        return value;
+      }
+      if (operation->right()->IsInteger32Constant()) {
+        *mask = operation->right()->GetInteger32Constant();
+        current = operation->left();
+      } else if (operation->left()->IsInteger32Constant()) {
+        *mask = operation->left()->GetInteger32Constant();
+        current = operation->right();
+      }
+      *context = operation->context();
+      return current;
+    } else {
+      return value;
+    }
+  }
+
+  return value;
+}
+
+
+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())) 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);
+
+  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());
+    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) {
+  int32_t and_mask;
+  int32_t or_mask;
+  HValue* context;
+  HValue* index_base = InductionVariableData::DecomposeBitwise(
+      check->index(), &and_mask, &or_mask, &context);
+
+  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_ = and_mask;
+    current_or_mask_in_block_ = 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 (and_mask != 0 &&
+      current_or_mask_in_block() == 0) {
+    if (current_and_mask_in_block() == 0 ||
+        and_mask > current_and_mask_in_block()) {
+      UseNewIndexInCurrentBlock(Token::BIT_AND, and_mask, index_base, context);
+      current_and_mask_in_block_ = and_mask;
+    }
+    check->set_skip_check();
+  }
+  if (current_and_mask_in_block() == 0) {
+    if (or_mask > current_or_mask_in_block()) {
+      UseNewIndexInCurrentBlock(Token::BIT_OR, or_mask, index_base, context);
+      current_or_mask_in_block_ = 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,
+                                                HValue* phi_operand) {

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

I think this code would be cleaner if all the match failures fall through to a
single case at the end which returns 0. The name "FindIncrement" or maybe
"MatchIncrement" might be better.

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

Done.

+  if (!phi_operand->representation().IsInteger32()) return 0;
+
+  if (phi_operand->IsAdd()) {
+    HAdd* operation = HAdd::cast(phi_operand);
+    if (operation->left() == phi) {
+      if (operation->right()->IsInteger32Constant()) {
+        return operation->right()->GetInteger32Constant();
+      } else {
+        return 0;
+      }
+    } else if (operation->right() == phi) {
+      if (operation->left()->IsInteger32Constant()) {
+        return operation->left()->GetInteger32Constant();
+      } else {
+        return 0;
+      }
+    } else {
+      return 0;
+    }
+  } else if (phi_operand->IsSub()) {
+    HSub* operation = HSub::cast(phi_operand);
+    if (operation->left() == phi) {
+      if (operation->right()->IsInteger32Constant()) {
+        return -operation->right()->GetInteger32Constant();
+      } else {
+        return 0;
+      }
+    } else {
+      return 0;
+    }
+  } else {
+    return 0;
+  }
+}
+
+
+HValue* InductionVariableData::DiscardOsrValue(HValue* v) {

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

"DiscardOsrValue" implies something is being deleted or removed. Maybe
"IgnoreOsrValue".

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

Done.

+  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 = DiscardOsrValue(v);
+  if (v->IsPhi()) {
+    return HPhi::cast(v)->induction_variable_data();
+  }
+  return NULL;
+}
+
+
+bool InductionVariableData::ValidateToken(Token::Value token) {

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

Validate the token how? This is not clear.

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

Renamed, and added comment.

+  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) &&
+      !phi()->block()->current_loop()->IsNestedInThisLoop(out_branch);
+}
+
+
+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->ValidateToken(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