Abcd for performance check.

src/hydrogen-instructions.cc

Index: src/hydrogen-instructions.cc
diff --git a/src/hydrogen-instructions.cc b/src/hydrogen-instructions.cc
index 36d1e11edab37c49aea9aa725866799eb28b83c6..ebff4de62fb55962358c1e35e00adc612e562be7 100644
--- a/src/hydrogen-instructions.cc
+++ b/src/hydrogen-instructions.cc
@@ -173,7 +173,7 @@ bool HValue::IsRelationTrue(NumericRelation relation,
                             HValue* other,
                             int offset,
                             int scale) {
-  if (this == other) {
+  if (ActualValue() == other->ActualValue()) {
     return scale == 0 && relation.IsExtendable(offset);
   }
 
@@ -187,14 +187,54 @@ bool HValue::IsRelationTrue(NumericRelation relation,
     return true;
   }
 
-  // Try decomposition (but do not accept scaled compounds).
+  // Try decomposition, but only if we are not scaled.
   DecompositionResult decomposition;
-  if (TryDecompose(&decomposition) &&
-      decomposition.scale() == 0 &&
-      decomposition.base()->IsRelationTrue(relation, other,
-                                           offset + decomposition.offset(),
-                                           scale)) {
-    return true;
+  if (scale == 0 && TryDecompose(&decomposition)) {
+    // Check if the compound is scaled.
+    if (decomposition.scale() == 0) {
+      // Non-scaled compounds can be handled normally.
+      if (decomposition.base()->IsRelationTrue(
+          relation, other, offset + decomposition.offset(), scale)) {
+        return true;
+      }
+    } else if (decomposition.offset() == 0 && offset == 0) {
+      // We only have a scale value which means that we can apply chaining
+      // using relation extensibility: negative scales grow values (positive
+      // direction), positive scales make them smaller (negative direction).
+      // As a concrete example: "(x << 1) <= 0" <== "x <= 0".
+      int direction = decomposition.scale() > 0 ? -1 : 1;

[Jakob Kummerow, 2013/04/17 11:34:15]

why not just "int direction = -decomposition.scale();"?

[Massi, 2013/05/07 11:32:03]

Done.

+      if (relation.IsExtendable(direction)
+          && decomposition.base()->IsRelationTrue(

[Jakob Kummerow, 2013/04/17 11:34:15]

nit: '&&' on the previous line please

[Massi, 2013/05/07 11:32:03]

Done.

+            relation, other, 0, 0)) {

[Jakob Kummerow, 2013/04/17 11:34:15]

nit: fits on last line?

[Massi, 2013/05/07 11:32:03]

Done.

+        return true;
+      }
+
+    } else {
+      // Just test for "same value" relation extensibility.
+
+      if (decomposition.base() == other) {
+        // The direction of the extensibility test is determined by scale and
+        // offset, but we can not handle all combinations.
+        int direction = 0;
+        // Do not accept left shifts greater than 1.
+        if (decomposition.scale() <= -1) {
+          if (decomposition.offset() == 0) {
+            // A positive scale makes values smaller.
+            direction = -decomposition.scale();
+          } else {
+            // If offset and scale have different signs they both go in the
+            // same direction, otherwise we cannot handle the combination.
+            if (decomposition.offset() * decomposition.scale() < 0) {
+              direction = offset;
+            }
+          }
+        }
+
+        if (direction != 0 && relation.IsExtendable(direction)) {
+          return true;
+        }
+      }
+    }
   }
 
   // Pass the request to the redefined value.
@@ -204,8 +244,13 @@ bool HValue::IsRelationTrue(NumericRelation relation,
 }
 
 
-bool HValue::TryGuaranteeRange(HValue* upper_bound) {
-  RangeEvaluationContext context = RangeEvaluationContext(this, upper_bound);
+bool HValue::TryGuaranteeRange(HValue* upper_bound,
+                               HBasicBlock* starting_block_for_hoisting) {
+  if (starting_block_for_hoisting == NULL) {
+    starting_block_for_hoisting = block();
+  }
+  RangeEvaluationContext context = RangeEvaluationContext(
+      this, upper_bound, starting_block_for_hoisting);
   TryGuaranteeRangeRecursive(&context);
   bool result = context.is_range_satisfied();
   if (result) {
@@ -259,8 +304,11 @@ void HValue::TryGuaranteeRangeRecursive(RangeEvaluationContext* context) {
 }
 
 
-RangeEvaluationContext::RangeEvaluationContext(HValue* value, HValue* upper)
-    : lower_bound_(upper->block()->graph()->GetConstant0()),
+RangeEvaluationContext::RangeEvaluationContext(HValue* value,
+                                               HValue* upper,
+                                               HBasicBlock* starting_block)
+    : starting_block_(starting_block),
+      lower_bound_(upper->block()->graph()->GetConstant0()),
       lower_bound_guarantee_(NULL),
       candidate_(value),
       upper_bound_(upper),
@@ -932,7 +980,8 @@ HNumericConstraint* HNumericConstraint::AddToGraph(
     HValue* constrained_value,
     NumericRelation relation,
     HValue* related_value,
-    HInstruction* insertion_point) {
+    HInstruction* insertion_point,
+    HBasicBlock* other_block) {
   if (insertion_point == NULL) {
     if (constrained_value->IsInstruction()) {
       insertion_point = HInstruction::cast(constrained_value);
@@ -944,7 +993,7 @@ HNumericConstraint* HNumericConstraint::AddToGraph(
   }
   HNumericConstraint* result =
       new(insertion_point->block()->zone()) HNumericConstraint(
-          constrained_value, relation, related_value);
+          constrained_value, relation, related_value, other_block);
   result->InsertAfter(insertion_point);
   return result;
 }
@@ -963,14 +1012,104 @@ HInductionVariableAnnotation* HInductionVariableAnnotation::AddToGraph(
     HPhi* phi,
     NumericRelation relation,
     int operand_index) {
-  HInductionVariableAnnotation* result =
-      new(phi->block()->zone()) HInductionVariableAnnotation(phi, relation,
-                                                             operand_index);
+  HInductionVariableAnnotation* result = new(phi->block()->zone())
+      HInductionVariableAnnotation(phi, relation, operand_index,
+                                   phi->block()->zone());
   result->InsertAfter(phi->block()->first());
   return result;
 }
 
 
+void HInductionVariableAnnotation::AddHoistedCheck(HBoundsCheck* check) {
+  hoisted_checks_.Add(check, block()->zone());
+}
+
+
+HInductionVariableAnnotation::HInductionVariableAnnotation(
+    HPhi* phi,
+    NumericRelation relation,
+    int operand_index,
+    Zone* zone)
+    : HUnaryOperation(phi), phi_(phi), relation_(relation),

[Jakob Kummerow, 2013/04/17 11:34:15]

nit: one line per initializer, please

[Massi, 2013/05/07 11:32:03]

Done.

+      operand_index_(operand_index), hoisted_checks_(4, zone) {
+}
+
+
+void HInductionVariableAnnotation::TryGuaranteeRangeChanging(
+    RangeEvaluationContext* context) {
+  if (relation().IsExtendable(1)) {
+    if (context->lower_bound_guarantee() == NULL) return;
+  } else {
+    return;
+  }
+
+  for (int i = 0; i < hoisted_checks()->length(); i++) {
+    HBoundsCheck* hoisted_check = hoisted_checks()->at(i);
+    if (hoisted_check->length()->ActualValue()
+        == context->upper_bound()->ActualValue()) {

[Jakob Kummerow, 2013/04/17 11:34:15]

nit: operator on the previous line

[Massi, 2013/05/07 11:32:03]

Done.

+      context->set_upper_bound_guarantee(hoisted_check);
+      return;
+    }
+  }
+
+  HBasicBlock* starting_block = context->starting_block();
+  HLoopInformation* starting_loop = starting_block->current_loop();
+  if (starting_loop == NULL) return;
+  HLoopInformation* my_loop = block()->current_loop();
+  if (my_loop == NULL) return;
+  if (my_loop->exits_count() > 1
+      && !block()->graph()->use_optimistic_licm()) return;

[Jakob Kummerow, 2013/04/17 11:34:15]

If it doesn't make a significant difference, I'd rather be careful than
optimistic here.

+
+  bool starting_loop_is_nested_in_my_loop = false;

[Jakob Kummerow, 2013/04/17 11:34:15]

we can make this loop a little simpler:
    // See if starting_loop is nested in my_loop.
    while (starting_loop != my_loop) {
      starting_loop = starting_loop->parent_loop();
      if (starting_loop == NULL) return;
    }
or you could just call "my_loop->IsInThisLoop(starting_loop);"

+  while (starting_loop != NULL) {
+    if (starting_loop == my_loop) {
+      starting_loop_is_nested_in_my_loop = true;
+      break;
+    }
+    starting_loop = starting_loop->parent_loop();
+  }
+  if (!starting_loop_is_nested_in_my_loop) return;
+  starting_loop = starting_block->current_loop();
+
+  for (HValue* candidate = context->candidate();
+       candidate != NULL;
+       candidate = candidate->RedefinedOperand()) {
+    if (candidate->IsNumericConstraint()) {

[Jakob Kummerow, 2013/04/17 11:34:15]

for consistency with code below, I'd transform this into:
if (!candidate->IsNumericConstraint()) continue;

[Massi, 2013/05/07 11:32:03]

Done.

+      HNumericConstraint* constraint = HNumericConstraint::cast(candidate);
+      if (!constraint->relation().IsExtendable(-1)) continue;
+      HLoopInformation* other_loop = constraint->other_block()->current_loop();
+      if (other_loop == my_loop) continue;
+
+      HBasicBlock* my_header = my_loop->loop_header();
+      HBasicBlock* my_pre_header = my_header->predecessors()->at(0);
+
+      HValue* induction_limit = constraint->related_value()->ActualValue();
+      HValue* upper_bound = context->upper_bound()->ActualValue();
+
+      if (induction_limit->block() != my_pre_header
+          && !induction_limit->block()->Dominates(my_pre_header)) continue;

[Jakob Kummerow, 2013/04/17 11:34:15]

nit: operator on the previous line

[Massi, 2013/05/07 11:32:03]

Done.

+      if (upper_bound->block() != my_pre_header
+          && !upper_bound->block()->Dominates(my_pre_header)) continue;

[Jakob Kummerow, 2013/04/17 11:34:15]

nit: operator on the previous line

[Massi, 2013/05/07 11:32:03]

Done.

+
+      if (!(induction_limit->representation().Equals(
+              upper_bound->representation())
+          || induction_limit->IsInteger32Constant())) {

[Jakob Kummerow, 2013/04/17 11:34:15]

nit: operator on the previous line

[Massi, 2013/05/07 11:32:03]

Done.

+        continue;
+      }
+
+      HBoundsCheck* check = new(block()->zone()) HBoundsCheck(
+          induction_limit, upper_bound);
+      check->InsertBefore(my_pre_header->end());
+      check->set_allow_equality(true);
+      check->UpdateRedefinedUses();
+      AddHoistedCheck(check);
+      context->set_upper_bound_guarantee(check);
+      return;
+    }
+  }
+}
+
+
 void HInductionVariableAnnotation::PrintDataTo(StringStream* stream) {
   stream->Add("(");
   RedefinedOperand()->PrintNameTo(stream);
@@ -1007,13 +1146,37 @@ void HBoundsCheck::TryGuaranteeRangeChanging(RangeEvaluationContext* context) {
     return;
   }
 
+  if (context->lower_bound_guarantee() != NULL &&
+      context->lower_bound_guarantee() != this) {
+    if (context->lower_bound_guarantee()->IsBoundsCheck()) {
+      HBoundsCheck* guarantee = HBoundsCheck::cast(
+          context->lower_bound_guarantee());
+      if (guarantee->base()->ActualValue() == base()->ActualValue()
+          && guarantee->scale() == scale()
+          && guarantee->offset() > offset()) {
+        context->set_lower_bound_guarantee(this);
+      }
+    }
+  } else if (context->upper_bound_guarantee() != NULL &&

[Jakob Kummerow, 2013/04/17 11:34:15]

I think the "else" needs to be removed.

[Massi, 2013/05/07 11:32:03]

Done.

[Massi, 2013/05/07 11:32:03]

Done.

+             context->upper_bound_guarantee() != this) {
+    if (context->upper_bound_guarantee()->IsBoundsCheck()) {
+      HBoundsCheck* guarantee = HBoundsCheck::cast(
+          context->upper_bound_guarantee());
+      if (guarantee->base()->ActualValue() == base()->ActualValue()
+          && guarantee->scale() == scale()
+          && guarantee->offset() < offset()) {
+        context->set_upper_bound_guarantee(this);
+      }
+    }
+  }
+
   // TODO(mmassi)
   // Instead of checking for "same basic block" we should check for
   // "dominates and postdominates".
   if (context->upper_bound() == length() &&
       context->lower_bound_guarantee() != NULL &&
       context->lower_bound_guarantee() != this &&
-      context->lower_bound_guarantee()->block() != block() &&
+      context->lower_bound_guarantee()->block() == block() &&
       offset() < context->offset() &&
       index_can_increase() &&
       context->upper_bound_guarantee() == NULL) {
@@ -1022,7 +1185,7 @@ void HBoundsCheck::TryGuaranteeRangeChanging(RangeEvaluationContext* context) {
     context->set_upper_bound_guarantee(this);
   } else if (context->upper_bound_guarantee() != NULL &&
              context->upper_bound_guarantee() != this &&
-             context->upper_bound_guarantee()->block() != block() &&
+             context->upper_bound_guarantee()->block() == block() &&
              offset() > context->offset() &&
              index_can_decrease() &&
              context->lower_bound_guarantee() == NULL) {
@@ -1034,7 +1197,7 @@ void HBoundsCheck::TryGuaranteeRangeChanging(RangeEvaluationContext* context) {
 
 
 void HBoundsCheck::ApplyIndexChange() {
-  if (skip_check()) return;
+  if (skip_check() || base() == NULL) return;
 
   DecompositionResult decomposition;
   bool index_is_decomposable = index()->TryDecompose(&decomposition);
@@ -1049,12 +1212,10 @@ void HBoundsCheck::ApplyIndexChange() {
   ReplaceAllUsesWith(index());
 
   HValue* current_index = decomposition.base();
-  int actual_offset = decomposition.offset() + offset();
-  int actual_scale = decomposition.scale() + scale();
 
-  if (actual_offset != 0) {
+  if (offset() != 0) {
     HConstant* add_offset = new(block()->graph()->zone()) HConstant(
-        actual_offset, index()->representation());
+          offset(), index()->representation());
     add_offset->InsertBefore(this);
     HInstruction* add = HAdd::New(block()->graph()->zone(),
         block()->graph()->GetInvalidContext(), current_index, add_offset);
@@ -1063,9 +1224,9 @@ void HBoundsCheck::ApplyIndexChange() {
     current_index = add;
   }
 
-  if (actual_scale != 0) {
+  if (scale() != 0) {
     HConstant* sar_scale = new(block()->graph()->zone()) HConstant(
-        actual_scale, index()->representation());
+        scale(), index()->representation());
     sar_scale->InsertBefore(this);
     HInstruction* sar = HSar::New(block()->graph()->zone(),
         block()->graph()->GetInvalidContext(), current_index, sar_scale);
@@ -1087,7 +1248,7 @@ 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())) {
+    if (index()->TryGuaranteeRange(length(), block())) {
       set_skip_check(true);
     }
     if (DetectCompoundIndex()) {
@@ -1163,6 +1324,8 @@ bool HBoundsCheckBaseIndexInformation::IsRelationTrueInternal(
     HValue* related_value,
     int offset,
     int scale) {
+  if (bounds_check() == NULL) return false;
+
   if (related_value == bounds_check()->length()) {
     return NumericRelation::Lt().CompoundImplies(
         relation,
@@ -1181,7 +1344,12 @@ void HBoundsCheckBaseIndexInformation::PrintDataTo(StringStream* stream) {
   stream->Add("base: ");
   base_index()->PrintNameTo(stream);
   stream->Add(", check: ");
-  base_index()->PrintNameTo(stream);
+  if (bounds_check() != NULL) {
+    bounds_check()->PrintNameTo(stream);
+  } else {
+    stream->Add("DISCONNECTED ");
+    OperandAt(1)->PrintNameTo(stream);
+  }
 }
 
 
@@ -2344,9 +2512,10 @@ void HCompareIDAndBranch::AddInformativeDefinitions() {
   NumericRelation r = NumericRelation::FromToken(token());
   if (r.IsNone()) return;
 
-  HNumericConstraint::AddToGraph(left(), r, right(), SuccessorAt(0)->first());
   HNumericConstraint::AddToGraph(
-        left(), r.Negated(), right(), SuccessorAt(1)->first());
+      left(), r, right(), SuccessorAt(0)->first(), SuccessorAt(1));
+  HNumericConstraint::AddToGraph(
+      left(), r.Negated(), right(), SuccessorAt(1)->first(), SuccessorAt(0));
 }
 
 
@@ -3038,6 +3207,40 @@ HValue* HAdd::EnsureAndPropagateNotMinusZero(BitVector* visited) {
 }
 
 
+bool HAdd::IsRelationTrueInternal(NumericRelation relation,
+                                  HValue* other,
+                                  int offset,
+                                  int scale) {
+  if (offset != 0 || scale != 0) return false;
+
+  // We look for a pattern like "x + delta rel x", where we should return
+  // true if "delta >= 0 && rel.IsExtendable(1)" or
+  // "delta <= 0 && rel.IsExtendable(-1)".
+  HValue* delta = NULL;
+  if (left()->ActualValue() == other->ActualValue()) {
+    delta = right();
+  } else if (right()->ActualValue() == other->ActualValue()) {
+    delta = left();
+  } else {
+    return false;
+  }
+
+  if (relation.IsExtendable(1)
+      && delta->IsRelationTrue(NumericRelation::Ge(),

[Jakob Kummerow, 2013/04/17 11:34:15]

nit: operator on the previous line

[Massi, 2013/05/07 11:32:03]

Done.

+                               block()->graph()->GetConstant0())) {
+    return true;
+  }
+
+  if (relation.IsExtendable(-1)
+      && delta->IsRelationTrue(NumericRelation::Le(),

[Jakob Kummerow, 2013/04/17 11:34:15]

nit: operator on the previous line

[Massi, 2013/05/07 11:32:03]

Done.

+                               block()->graph()->GetConstant0())) {
+    return true;
+  }
+
+  return false;
+}
+
+
 bool HStoreKeyed::NeedsCanonicalization() {
   // If value is an integer or smi or comes from the result of a keyed load or
   // constant then it is either be a non-hole value or in the case of a constant