Abcd for performance check.

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 50 matching lines @@
     case kDouble: return "d";
     case kInteger32: return "i";
     case kExternal: return "x";
     default:
       UNREACHABLE();
       return NULL;
   }
 }
 
 
+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 };
   return weights[Min(block()->LoopNestingDepth(),
                      static_cast<int>(ARRAY_SIZE(weights)-1))];
 }
 
 
 Isolate* HValue::isolate() const {
   ASSERT(block() != NULL);
@@ skipping 79 matching lines @@
 void HValue::AddDependantsToWorklist(HInferRepresentation* h_infer) {
   for (HUseIterator it(uses()); !it.Done(); it.Advance()) {
     h_infer->AddToWorklist(it.value());
   }
   for (int i = 0; i < OperandCount(); ++i) {
     h_infer->AddToWorklist(OperandAt(i));
   }
 }
 
 
-// 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.
   if (IsRelationTrueInternal(relation, other, offset, scale)) return true;
 
   // If scale is 0 try the reversed relation.
   if (scale == 0 &&
       // TODO(mmassi): do we need the full, recursive IsRelationTrue?
       other->IsRelationTrueInternal(relation.Reversed(), this, -offset)) {
     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.
   HValue* redefined = RedefinedOperand();
   return redefined != NULL && redefined->IsRelationTrue(relation, other,
                                                         offset, scale);
 }
 
 
-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;
 }
 
 
 void HValue::TryGuaranteeRangeRecursive(RangeEvaluationContext* context) {
   // Check if we already know that this value satisfies the lower bound.
   if (context->lower_bound_guarantee() == NULL) {
     if (IsRelationTrueInternal(NumericRelation::Ge(), context->lower_bound(),
                                context->offset(), context->scale())) {
       context->set_lower_bound_guarantee(this);
@@ skipping 27 matching lines @@
     context->swap_candidate(&decomposition);
   }
   if (context->is_range_satisfied()) return;
 
   // Try to modify this to satisfy the constraint.
 
   TryGuaranteeRangeChanging(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),
       upper_bound_guarantee_(NULL),
       offset_(0),
       scale_(0) {
 }
 
 
 HValue* RangeEvaluationContext::ConvertGuarantee(HValue* guarantee) {
@@ skipping 651 matching lines @@
     }
   }
 }
 #endif
 
 
 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);
     } else if (constrained_value->IsPhi()) {
       insertion_point = constrained_value->block()->first();
     } else {
       UNREACHABLE();
     }
   }
   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;
 }
 
 
 void HNumericConstraint::PrintDataTo(StringStream* stream) {
   stream->Add("(");
   constrained_value()->PrintNameTo(stream);
   stream->Add(" %s ", relation().Mnemonic());
   related_value()->PrintNameTo(stream);
   stream->Add(")");
 }
 
 
 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);
   stream->Add(" %s ", relation().Mnemonic());
   induction_base()->PrintNameTo(stream);
   stream->Add(")");
 }
 
 
 void HDummyUse::PrintDataTo(StringStream* stream) {
@@ skipping 16 matching lines @@
   stream->Add("#%d", argument_count());
 }
 
 
 void HBoundsCheck::TryGuaranteeRangeChanging(RangeEvaluationContext* context) {
   if (context->candidate()->ActualValue() != base()->ActualValue() ||
       context->scale() < scale()) {
     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);
   if (index_is_decomposable) {
     ASSERT(decomposition.base() == base());
     if (decomposition.offset() == offset() &&
         decomposition.scale() == scale()) return;
   } else {
     return;
   }
 
   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);
     add->InsertBefore(this);
     add->AssumeRepresentation(index()->representation());
     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);
     sar->InsertBefore(this);
     sar->AssumeRepresentation(index()->representation());
     current_index = sar;
   }
 
   SetOperandAt(0, current_index);
 
   base_ = NULL;
   offset_ = 0;
   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);
-    }
-    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);
   }
 }
 
 
 bool HBoundsCheck::IsRelationTrueInternal(NumericRelation relation,
                                           HValue* related_value,
                                           int offset,
                                           int scale) {
   if (related_value == length()) {
     // A HBoundsCheck is smaller than the length it compared against.
@@ skipping 47 matching lines @@
   }
   UpdateRepresentation(r, h_infer, "boundscheck");
 }
 
 
 bool HBoundsCheckBaseIndexInformation::IsRelationTrueInternal(
     NumericRelation relation,
     HValue* related_value,
     int offset,
     int scale) {
+  if (bounds_check() == NULL) return false;
+
   if (related_value == bounds_check()->length()) {
     return NumericRelation::Lt().CompoundImplies(
         relation,
         bounds_check()->offset(), bounds_check()->scale(), offset, scale);
   } else if (related_value == block()->graph()->GetConstant0()) {
     return NumericRelation::Ge().CompoundImplies(
         relation,
         bounds_check()->offset(), bounds_check()->scale(), offset, scale);
   } else {
     return false;
   }
 }
 
 
 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);
+  }
 }
 
 
 void HCallConstantFunction::PrintDataTo(StringStream* stream) {
   if (IsApplyFunction()) {
     stream->Add("optimized apply ");
   } else {
     stream->Add("%o ", function()->shared()->DebugName());
   }
   stream->Add("#%d", argument_count());
@@ skipping 610 matching lines @@
       ClearFlag(HValue::kCanBeDivByZero);
     }
     return result;
   } else {
     return HValue::InferRange(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() ||
         OperandAt(1)->block()->is_osr_entry()) return;
 
     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
       // its first input is greater than the phi itself, then that must be
       // the back edge, and the phi is always greater than its second input.
       for (int relation_index = 0; relation_index < 2; relation_index++) {
         if (OperandAt(operand_index)->IsRelationTrue(relations[relation_index],
                                                      this)) {
           HInductionVariableAnnotation::AddToGraph(this,
                                                    relations[relation_index],
@@ skipping 500 matching lines @@
   stream->Add(Token::Name(token()));
   stream->Add(" ");
   HControlInstruction::PrintDataTo(stream);
 }
 
 
 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));
 }
 
 
 void HCompareIDAndBranch::PrintDataTo(StringStream* stream) {
   stream->Add(Token::Name(token()));
   stream->Add(" ");
   left()->PrintNameTo(stream);
   stream->Add(" ");
   right()->PrintNameTo(stream);
   HControlInstruction::PrintDataTo(stream);
@@ skipping 671 matching lines @@
   visited->Add(id());
   // Propagate to the left argument. If the left argument cannot be -0, then
   // the result of the sub operation cannot be either.
   if (range() == NULL || range()->CanBeMinusZero()) {
     return left();
   }
   return NULL;
 }
 
 
+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
   // the hole is only being stored explicitly: no need for canonicalization.
   //
   // The exception to that is keyed loads from external float or double arrays:
   // these can load arbitrary representation of NaN.
 
   if (value()->IsConstant()) {
     return false;
@@ skipping 482 matching lines @@
 
 
 void HCheckFunction::Verify() {
   HInstruction::Verify();
   ASSERT(HasNoUses());
 }
 
 #endif
 
 } }  // namespace v8::internal