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..e552bd86591f8eb67bb61ed1263b454f0963be20 100644
--- a/src/hydrogen-instructions.cc
+++ b/src/hydrogen-instructions.cc
@@ -68,6 +68,88 @@ const char* Representation::Mnemonic() const {
 }
 
 
+bool NumericRelationTable::IsInTable(int value_id,
+                                     NumericRelation relation,
+                                     int other_value_id,
+                                     int offset,
+                                     int scale,
+                                     int block_id,
+                                     bool* result) {
+  NumericRelationTableElement element(value_id, relation, other_value_id,
+                                      offset, scale, block_id, false);
+  int index = FindInsertionPoint(element, result);
+  return index < 0;
+}
+
+
+void NumericRelationTable::AddToTable(int value_id,
+                                      NumericRelation relation,
+                                      int other_value_id,
+                                      int offset,
+                                      int scale,
+                                      int block_id,
+                                      bool result) {
+  NumericRelationTableElement element(value_id, relation, other_value_id,
+                                      offset, scale, block_id, result);
+  bool res;
+  int index = FindInsertionPoint(element, &res);
+  if (index >= 0) {
+    Insert(element, index);
+  }
+}
+
+
+void NumericRelationTable::Clear() {
+  table_.Clear();
+}
+
+
+int NumericRelationTable::FindInsertionPoint(
+    const NumericRelationTableElement& element,
+    bool* result) {
+  int lower = 0;
+  int upper = table_.length();
+  if (upper == 0) return 0;
+
+  while (true) {
+    int middle = (lower + upper) >> 1;
+
+    int comparison = element.Compare(table_.at(middle));
+    if (comparison > 0) {
+      if (lower == middle) {
+        if (upper < table_.length()) {
+          if (element.Compare(table_.at(upper)) == 0) {
+            *result = table_.at(upper).result();
+            return -1;
+          } else {
+            return upper;
+          }
+        } else {
+          return upper;
+        }
+      } else {
+        lower = middle;
+      }
+    } else if (comparison < 0) {
+      if (upper == middle) {
+        return middle;
+      } else {
+        upper = middle;
+      }
+    } else {
+      *result = table_.at(middle).result();
+      return -1;
+    }
+  }
+}
+
+
+void NumericRelationTable::Insert(const NumericRelationTableElement& element,
+                                  int index) {
+  table_.InsertAt(index, element, zone_);
+}
+
+
 int HValue::LoopWeight() const {
   const int w = FLAG_loop_weight;
   static const int weights[] = { 1, w, w*w, w*w*w, w*w*w*w };
@@ -167,14 +249,34 @@ void HValue::AddDependantsToWorklist(HInferRepresentation* h_infer) {
 }
 
 
-// This method is recursive but it is guaranteed to terminate because
-// RedefinedOperand() always dominates "this".
 bool HValue::IsRelationTrue(NumericRelation relation,
                             HValue* other,
                             int offset,
                             int scale) {
-  if (this == other) {
-    return scale == 0 && relation.IsExtendable(offset);
+  bool result;
+  if (block()->graph()->HasRelationBeenEvaluated(
+      this, relation, other, offset, scale, block(), &result)) {
+    return result;
+  }
+
+  result = EvaluateRelationRecursively(relation, other, offset, scale);
+
+  block()->graph()->AddRelationToTable(
+      this, relation, other, offset, scale, block(), result);
+  return result;
+}
+
+
+// This method is a recursive graph walk but it is guaranteed to terminate
+// because RedefinedOperand() always dominates "this" and phis will check
+// the "kNumericConstraintEvaluationInProgress" flag and never re-evaluate
+// themselves.
+bool HValue::EvaluateRelationRecursively(NumericRelation relation,
+                                         HValue* other,
+                                         int offset,
+                                         int scale) {
+  if (ActualValue() == other->ActualValue()) {
+    return scale == 0 && relation.ImpliedByEquality(offset);
   }
 
   // Test the direct relation.
@@ -187,14 +289,53 @@ 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();
+      if (relation.IsExtendable(direction) &&
+          decomposition.base()->IsRelationTrue(relation, other, 0, 0)) {
+        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 (relation.ImpliedByEquality(direction)) {
+          return true;
+        }
+      }
+    }
   }
 
   // Pass the request to the redefined value.
@@ -204,14 +345,37 @@ 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();
+  }
+
+  bool lower_done, upper_done, lower_result, upper_result;
+  lower_done = block()->graph()->HasRelationBeenEvaluated(
+      this, NumericRelation::Ge(), block()->graph()->GetConstant0(),
+      0, 0, starting_block_for_hoisting, &lower_result);
+  upper_done = block()->graph()->HasRelationBeenEvaluated(
+      this, NumericRelation::Lt(), upper_bound,
+      0, 0, starting_block_for_hoisting, &upper_result);
+  if (lower_done && upper_done) return lower_result && upper_result;
+
+  RangeEvaluationContext context = RangeEvaluationContext(
+      this, upper_bound, starting_block_for_hoisting);
   TryGuaranteeRangeRecursive(&context);
   bool result = context.is_range_satisfied();
   if (result) {
     context.lower_bound_guarantee()->SetResponsibilityForRange(DIRECTION_LOWER);
     context.upper_bound_guarantee()->SetResponsibilityForRange(DIRECTION_UPPER);
   }
+
+  block()->graph()->AddRelationToTable(
+      this, NumericRelation::Ge(), block()->graph()->GetConstant0(), 0, 0,
+      starting_block_for_hoisting, context.lower_bound_guarantee() != NULL);
+  block()->graph()->AddRelationToTable(
+      this, NumericRelation::Lt(), upper_bound, 0, 0,
+      starting_block_for_hoisting, context.upper_bound_guarantee() != NULL);
+
   return result;
 }
 
@@ -259,8 +423,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 +1099,8 @@ HNumericConstraint* HNumericConstraint::AddToGraph(
     HValue* constrained_value,
     NumericRelation relation,
     HValue* related_value,
-    HInstruction* insertion_point) {
+    HInstruction* insertion_point,
+    HBasicBlock* jump_target_when_false) {
   if (insertion_point == NULL) {
     if (constrained_value->IsInstruction()) {
       insertion_point = HInstruction::cast(constrained_value);
@@ -944,7 +1112,7 @@ HNumericConstraint* HNumericConstraint::AddToGraph(
   }
   HNumericConstraint* result =
       new(insertion_point->block()->zone()) HNumericConstraint(
-          constrained_value, relation, related_value);
+          constrained_value, relation, related_value, jump_target_when_false);
   result->InsertAfter(insertion_point);
   return result;
 }
@@ -963,14 +1131,100 @@ 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),
+      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()) {
+      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;
+  if (!my_loop->IsNestedInThisLoop(starting_loop)) return;
+
+  for (HValue* candidate = context->candidate();
+       candidate != NULL;
+       candidate = candidate->RedefinedOperand()) {
+    if (!candidate->IsNumericConstraint()) continue;
+
+    HNumericConstraint* constraint = HNumericConstraint::cast(candidate);
+    if (!constraint->relation().IsExtendable(-1)) continue;
+    HLoopInformation* other_loop =
+        constraint->jump_target_when_false()->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/05/15 12:56:35]

another nit: {} please when the condition doesn't fit onto a single line. Again
below.

[Massi, 2013/05/21 12:49:56]

Done.

+    if (upper_bound->block() != my_pre_header &&
+        !upper_bound->block()->Dominates(my_pre_header)) continue;
+
+    if (!(induction_limit->representation().Equals(
+            upper_bound->representation()) ||
+        induction_limit->IsInteger32Constant())) {
+      continue;
+    }
+
+    block()->graph()->ClearRelationsTable();
+
+    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,34 +1261,62 @@ void HBoundsCheck::TryGuaranteeRangeChanging(RangeEvaluationContext* context) {
     return;
   }
 
+  // Make so that the strongest possible checks are used as guarantees.
+  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);
+      }
+    }
+  }
+  if (context->upper_bound_guarantee() != NULL &&
+      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) {
     offset_ = context->offset();
     SetResponsibilityForRange(DIRECTION_UPPER);
     context->set_upper_bound_guarantee(this);
+    block()->graph()->ClearRelationsTable();
   } 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) {
     offset_ = context->offset();
     SetResponsibilityForRange(DIRECTION_LOWER);
     context->set_lower_bound_guarantee(this);
+    block()->graph()->ClearRelationsTable();
   }
 }
 
 
 void HBoundsCheck::ApplyIndexChange() {
-  if (skip_check()) return;
+  if (skip_check() || base() == NULL) return;
 
   DecompositionResult decomposition;
   bool index_is_decomposable = index()->TryDecompose(&decomposition);
@@ -1049,12 +1331,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 +1343,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);
@@ -1084,18 +1364,11 @@ void HBoundsCheck::ApplyIndexChange() {
 
 
 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);
-    }
-    if (DetectCompoundIndex()) {
-      HBoundsCheckBaseIndexInformation* base_index_info =
-          new(block()->graph()->zone())
-          HBoundsCheckBaseIndexInformation(this);
-      base_index_info->InsertAfter(this);
-    }
+  if (DetectCompoundIndex()) {
+    HBoundsCheckBaseIndexInformation* base_index_info =
+        new(block()->graph()->zone())
+        HBoundsCheckBaseIndexInformation(this);
+    base_index_info->InsertAfter(this);
   }
 }
 
@@ -1163,6 +1436,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 +1456,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);
+  }
 }
 
 
@@ -1812,7 +2092,9 @@ Range* HMod::InferRange(Zone* zone) {
 
 
 void HPhi::AddInformativeDefinitions() {
-  if (OperandCount() == 2) {
+  HLoopInformation* my_loop = block()->current_loop();
+
+  if (OperandCount() == 2 && my_loop != NULL) {
     // If one of the operands is an OSR block give up (this cannot be an
     // induction variable).
     if (OperandAt(0)->block()->is_osr_entry() ||
@@ -1821,9 +2103,16 @@ void HPhi::AddInformativeDefinitions() {
     for (int operand_index = 0; operand_index < 2; operand_index++) {
       int other_operand_index = (operand_index + 1) % 2;
 
+      HValue* induction_base_cantidate = OperandAt(other_operand_index);

[Jakob Kummerow, 2013/05/15 12:56:35]

nit: s/cantidate/candidate/

[Massi, 2013/05/21 12:49:56]

Done.

+      HLoopInformation* base_block_loop =
+          induction_base_cantidate->block()->current_loop();
+      if (base_block_loop != NULL &&
+          (base_block_loop == my_loop ||
+           base_block_loop->IsNestedInThisLoop(my_loop))) continue;
+
       static NumericRelation relations[] = {
-        NumericRelation::Ge(),
-        NumericRelation::Le()
+        NumericRelation::Gt(),
+        NumericRelation::Lt()
       };
 
       // Check if this phi is an induction variable. If, e.g., we know that
@@ -2344,9 +2633,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 +3328,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(),
+                            block()->graph()->GetConstant0())) {
+    return true;
+  }
+
+  if (relation.IsExtendable(-1) &&
+      delta->IsRelationTrue(NumericRelation::Le(),
+                            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