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 155 matching lines @@
   }
 }
 
 
 // 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) {
+  if (ActualValue() == other->ActualValue()) {
     return scale == 0 && relation.IsExtendable(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() > 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.
   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();
+  }
+  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);
   }
   return result;
 }
 
 
@@ skipping 33 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* other_block) {
   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, other_block);
   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),

[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);
   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;
   }
 
+  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) {
     offset_ = context->offset();
     SetResponsibilityForRange(DIRECTION_UPPER);
     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) {
     offset_ = context->offset();
     SetResponsibilityForRange(DIRECTION_LOWER);
     context->set_lower_bound_guarantee(this);
   }
 }
 
 
 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())) {
+    if (index()->TryGuaranteeRange(length(), block())) {
       set_skip_check(true);
     }
     if (DetectCompoundIndex()) {
       HBoundsCheckBaseIndexInformation* base_index_info =
           new(block()->graph()->zone())
           HBoundsCheckBaseIndexInformation(this);
       base_index_info->InsertAfter(this);
     }
   }
 }
@@ skipping 55 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 1142 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(),

[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
   // 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