Handling expression decomposition and array bounds check hoisting: working code with lots of debugg…

src/hydrogen-instructions.cc

Index: src/hydrogen-instructions.cc
diff --git a/src/hydrogen-instructions.cc b/src/hydrogen-instructions.cc
index 52eada41f5df8213abaaa369fcd8aa1f9d549ea5..34a59848579e7ee995ebe72688f238280b4bf510 100644
--- a/src/hydrogen-instructions.cc
+++ b/src/hydrogen-instructions.cc
@@ -160,6 +160,122 @@ void HValue::AddDependantsToWorklist(HInferRepresentation* h_infer) {
 }
 
 
+bool HValue::TryGuaranteeRange(HValue* upper_bound) {
+  RangeEvaluationContext context = RangeEvaluationContext(this, upper_bound);
+  TryGuaranteeRangeRecursive(&context);
+  return context.RangeSatisfied();
+}
+
+
+void HValue::TryGuaranteeRangeRecursive(RangeEvaluationContext* context) {
+
+  if (FLAG_log_abcd) {
+  PrintF(" +++ TryGuaranteeRangeRecursive(");
+  SimplyPrint();
+  PrintF(") {[LOWER ");
+  if (context->lower_check_satisfied()) {
+    context->lower_check_guarantee()->SimplyPrint();
+  } else {
+    PrintF("NULL");
+  }
+  PrintF("] ");
+  context->lower_bound()->SimplyPrint();
+  PrintF(" <= ((x + %d) >> %d) ", context->offset(), context->scale());
+  context->upper_bound()->SimplyPrint();
+  PrintF(" [UPPER ");
+  if (context->upper_check_satisfied()) {
+    context->upper_check_guarantee()->SimplyPrint();
+  } else {
+    PrintF("NULL");
+  }
+  PrintF("]}\n");
+  }
+
+
+  // Try to satisfy the lower bound on this value

[Jakob Kummerow, 2013/03/11 11:55:02]

better comment:
// Check if we already know that this value satisfies the lower bound.

+  if (!context->lower_check_satisfied()) {
+    if (IsRelationTrueInternal(NumericRelation::Ge(), context->lower_bound(),
+                               context->offset(), context->scale())) {
+
+      if (FLAG_log_abcd)
+      PrintF(" ___ TryGuaranteeRangeRecursive(LOWER TRUE)\n");
+
+      context->set_lower_check_guarantee(this);
+    }
+  }
+
+  // Try to satisfy the upper bound on this value

[Jakob Kummerow, 2013/03/11 11:55:02]

better comment:
// Check if we already know that this value satisfies the upper bound.

+  if (!context->upper_check_satisfied()) {
+    if (IsRelationTrueInternal(NumericRelation::Lt(), context->upper_bound(),
+                               context->offset(), context->scale()) ||
+        (context->scale() == 0 &&
+         context->upper_bound()->IsRelationTrue(NumericRelation::Gt(),
+                                                this, -context->offset()))) {
+
+      if (FLAG_log_abcd)
+      PrintF(" ___ TryGuaranteeRangeRecursive(UPPER TRUE)\n");
+
+      context->set_upper_check_guarantee(this);
+    }
+  }
+
+  if (context->RangeSatisfied()) return;
+
+  // See if our RedefinedOperand() satisfies the constraints.
+  if (RedefinedOperand() != NULL) {
+    RedefinedOperand()->TryGuaranteeRangeRecursive(context);
+  }
+  if (context->RangeSatisfied()) return;
+
+  // See if the constraints can be satisfied by decomposition.

[Jakob Kummerow, 2013/03/11 11:55:02]

Why does this need to happen in the recursive call (and therefore possibly
several times)? I think the entire "try decomposition" block should go into the
entry function, TryGuaranteeRange(), and should work on |this| there as opposed
to context->origin().
That would also mean that you don't need to swap the context's entries.

[Massi, 2013/03/13 15:58:14]

Because every definition of this value could be decomposable.
In practice iDefs will never be decomposable, only the actual HAdd or HSar will,
but we must try them all to findthe right one.
A failed call to TryDecompose is relatively cheap: just a virtual call to a
method that returns false.

[Jakob Kummerow, 2013/03/14 12:50:08]

OK, I see.

+  HValue* base = NULL;
+  int offset = context->offset();
+  int scale = context->scale();
+  if (context->origin()->TryDecompose(&base, &offset, &scale)) {
+    context->swap_origin(base, offset, scale);
+
+    if (FLAG_log_abcd)
+    PrintF(" ___ TryGuaranteeRangeRecursive(DECOMPOSE START)\n");
+
+    context->origin()->TryGuaranteeRangeRecursive(context);
+
+    if (FLAG_log_abcd)
+    PrintF(" ___ TryGuaranteeRangeRecursive(DECOMPOSE END [%s])\n",
+           context->RangeSatisfied() ? "!" : "x");
+
+    context->swap_origin(base, offset, scale);
+  }
+  if (context->RangeSatisfied()) return;
+
+  // Try to modify this to satisfy the constraint.
+  TryGuaranteeRangeInner(context);
+
+  if (FLAG_log_abcd) {
+  PrintF(" >>> TryGuaranteeRangeRecursive(");
+  SimplyPrint();
+  PrintF("): %s\n", context->RangeSatisfied() ? "TRUE" : "FALSE");
+  }
+}
+
+
+HValue::RangeEvaluationContext::RangeEvaluationContext(
+    HValue* value, HValue* upper)

[Jakob Kummerow, 2013/03/11 11:55:02]

for method/function declarations (as opposed to calls), please put every
argument on its own line (unless everything, including the method name, fits
onto a single line).

+    : lower_bound_(upper->block()->graph()->GetConstant0()),
+      lower_check_guarantee_(NULL),
+      origin_(value),
+      upper_bound_(upper),
+      upper_check_guarantee_(NULL),
+      offset_(0), scale_(0) {

[Jakob Kummerow, 2013/03/11 11:55:02]

let's give each initializer its own line.

+}
+
+
+HValue* HValue::RangeEvaluationContext::ConvertGuarantee(HValue* guarantee) {

[Jakob Kummerow, 2013/03/11 11:55:02]

This method is simple enough to live in the .h file (if you want).

[Massi, 2013/03/13 15:58:14]

But it needs to access HBoundsCheckBaseIndexInformation::cast which is not
defined yet.

+  return guarantee->IsBoundsCheckBaseIndexInformation()
+      ? HBoundsCheckBaseIndexInformation::cast(guarantee)->bounds_check()
+      : guarantee;
+}
+
+
 static int32_t ConvertAndSetOverflow(int64_t result, bool* overflow) {
   if (result > kMaxInt) {
     *overflow = true;
@@ -782,6 +898,17 @@ void HInstruction::Verify() {
           cur = cur->previous();
         }
         // Must reach other operand in the same block!
+
+        if (cur != other_operand) {
+          PrintF("\n !!! !!! !!! !!! !!! ASSERT([BLOCK %d]",
+                 other_operand->block()->block_id());
+          other_operand->SimplyPrint();
+          PrintF(" used in index %d does not dominate [BLOCK %d]",
+                 i, block()->block_id());
+          SimplyPrint();
+          PrintF(")\n");
+        }
+
         ASSERT(cur == other_operand);
       }
     } else {
@@ -885,25 +1012,188 @@ void HBinaryCall::PrintDataTo(StringStream* stream) {
 }
 
 
+void HBoundsCheck::TryGuaranteeRangeInner(RangeEvaluationContext* context) {
+  if (FLAG_log_abcd) {
+  PrintF(" +++ HBoundsCheck::TryGuaranteeRangeInner(");
+  SimplyPrint();
+  PrintF(" [LOWER ");
+  if (context->lower_check_satisfied()) {
+    context->lower_check_guarantee()->SimplyPrint();
+  } else {
+    PrintF("NULL");
+  }
+  PrintF("] [UPPER ");
+  if (context->upper_check_satisfied()) {
+    context->upper_check_guarantee()->SimplyPrint();
+  } else {
+    PrintF("NULL");
+  }
+  PrintF("])\n");
+  }
+
+  if (context->origin()->ActualValue() == base()->ActualValue() &&

[Jakob Kummerow, 2013/03/11 11:55:02]

nit: you can avoid one level of nested conditions here by turning this into an
early return:

  if (context->origin()->ActualValue() != base()->ActualValue() ||
      context->scale() < scale()) {
    return;
  }

+      context->scale() >= scale()) {
+    if (index_has_not_been_changed()) {
+      if (offset() < context->offset()) {
+        change_direction_ = 1;

[Jakob Kummerow, 2013/03/11 11:55:02]

It doesn't seem right that we're always setting change_direction_ here, even if
we won't do anything below because none of the if-conditions are satisfied. I
think this block here (lines 1036-1042) should be removed. (You're setting
change_direction_ below anyway when necessary.)

+      } else if (offset() > context->offset()) {
+        change_direction_ = -1;
+      }
+    }
+
+    if (context->upper_bound() == length() &&
+        context->lower_check_satisfied() &&
+        context->lower_check_guarantee() != this &&
+        index_can_increase() &&
+        !context->upper_check_satisfied()) {
+      if (offset() < context->offset()) {

[Jakob Kummerow, 2013/03/11 11:55:02]

Since this condition doesn't have an else-branch, you can fold it into the
previous condition ("... && offset_ < context->offset()").

+
+        if (FLAG_log_abcd)
+        PrintF(" ___ HBoundsCheck::TryGuaranteeRangeInner(%s%d CHANGE UPPER(base %s%d[%s%d][%d]), offset %d (was %d), scale %d)\n",
+               representation().Mnemonic(), id(),
+               base()->representation().Mnemonic(), base()->id(),
+               base()->ActualValue()->representation().Mnemonic(), base()->ActualValue()->id(),
+               change_direction_, context->offset(), offset(), scale());
+
+        offset_ = context->offset();
+        change_direction_ = 1;

[Jakob Kummerow, 2013/03/11 11:55:02]

To make it more obvious that this is closely related to index_can_increase(),
I'd introduce a setter function set_index_must_increase().

+        context->set_upper_check_guarantee(this);
+      }
+    } else if (context->upper_check_satisfied() &&
+               context->upper_check_guarantee() != this &&
+               index_can_decrease() &&
+               !context->lower_check_satisfied()) {
+      if (offset() > context->offset()) {
+
+        if (FLAG_log_abcd)
+        PrintF(" ___ HBoundsCheck::TryGuaranteeRangeInner(%s%d CHANGE LOWER(base %s%d[%s%d][%d]), offset %d (was %d), scale %d)\n",
+               representation().Mnemonic(), id(),
+               base()->representation().Mnemonic(), base()->id(),
+               base()->ActualValue()->representation().Mnemonic(), base()->ActualValue()->id(),
+               change_direction_, context->offset(), offset(), scale());
+
+        offset_ = context->offset();
+        change_direction_ = -1;
+        context->set_lower_check_guarantee(this);
+      }
+    }
+  }
+}
+
+
+void HBoundsCheck::ApplyIndexChange() {
+  if (HasOriginalIndex() || skip_check()) return;

[Jakob Kummerow, 2013/03/11 11:55:02]

HasOriginalIndex() potentially performs the "index()->TryDecompose(..)" step,
which we'll do again below. Since this is the only call site of HasOriginalIndex
AFAICS, there should be no obstacles to removing this duplication of effort.

+
+  HValue* base_index = NULL;

[Jakob Kummerow, 2013/03/11 11:55:02]

I think you mean index_base, index_offset, index_scale here.

+  int base_offset = 0;
+  int base_scale = 0;
+  if (!index()->TryDecompose(&base_index, &base_offset, &base_scale)) return;
+
+  ReplaceAllUsesWith(index());
+
+  HValue* current_index = base_index;
+  int actual_offset = base_offset + offset();
+  int actual_scale = base_scale + scale();
+
+  if (actual_offset != 0) {
+    HConstant* add_offset = new(block()->graph()->zone()) HConstant(
+        actual_offset, index()->representation());
+    add_offset->InsertBefore(this);
+    HAdd* add = new(block()->graph()->zone()) HAdd(
+        block()->graph()->GetInvalidContext(), current_index, add_offset);
+    add->InsertBefore(this);
+    add->AssumeRepresentation(index()->representation());
+    current_index = add;
+  }
+
+  if (actual_scale != 0) {
+    HConstant* sar_scale = new(block()->graph()->zone()) HConstant(
+        actual_scale, index()->representation());
+    sar_scale->InsertBefore(this);
+    HSar* sar = new(block()->graph()->zone()) HSar(
+        block()->graph()->GetInvalidContext(), current_index, sar_scale);
+    sar->InsertBefore(this);
+    sar->AssumeRepresentation(index()->representation());
+    current_index = sar;
+  }
+
+
+  if (FLAG_log_abcd)
+  PrintF("\n !!! !!! !!! HBoundsCheck::ApplyIndexChange(%s%d, index %s%d becomes ((%s%d + %d) >> %d)\n",
+         representation().Mnemonic(), id(),
+         index()->representation().Mnemonic(), index()->id(),
+         current_index->representation().Mnemonic(), current_index->id(),
+         offset(), scale());
+
+  SetOperandAt(0, current_index);
+
+  PrintF(" ");
+
+  base_ = NULL;

[Jakob Kummerow, 2013/03/11 11:55:02]

Is it necessary to do this cleanup?

[Massi, 2013/03/13 15:58:14]

In principle, no, but I don't like leaving meaningless values around...

[Jakob Kummerow, 2013/03/14 12:50:08]

I disagree with this reasoning. Resetting those values wastes CPU cycles. Since
we're not going to read them anymore, we don't care what they store. So please
skip the cleanup.

+  offset_ = 0;
+  scale_ = 0;
+  change_direction_ = 0;
+}
+
+
 void HBoundsCheck::AddInformativeDefinitions() {
   // TODO(mmassi): Executing this code during AddInformativeDefinitions
   // is a hack. Move it to some other HPhase.
-  if (index()->IsRelationTrue(NumericRelation::Ge(),
-                              block()->graph()->GetConstant0()) &&
-      index()->IsRelationTrue(NumericRelation::Lt(), length())) {
-    set_skip_check(true);
+  if (FLAG_new_abcd) {
+
+    if (FLAG_log_abcd) {
+    PrintF("\n +++ >>> >>> >>> HBoundsCheck::AddInformativeDefinitions[BLOCK %d](",
+           block()->block_id());
+    SimplyPrint();
+    PrintF(") CHANGE FOR LENGTH %s%d\n",
+           length()->representation().Mnemonic(), length()->id());
+
+    if (index()->TryGuaranteeRange(length())) {

[Jakob Kummerow, 2013/03/11 11:55:02]

This should *not* be inside the if(FLAG_log_abcd) block!

+      set_skip_check(true);
+    }
+    }
+
+    if (DetectCompoundIndex()) {
+      HBoundsCheckBaseIndexInformation* base_index_info =
+          new(block()->graph()->zone())
+          HBoundsCheckBaseIndexInformation(this);
+      base_index_info->InsertAfter(this);
+    }
+
+    if (FLAG_log_abcd) {
+    PrintF(" +++ <<< <<< <<< HBoundsCheck::AddInformativeDefinitions[BLOCK %d](",
+           block()->block_id());
+    SimplyPrint();
+    if (base() != index()) {
+      PrintF("{base %s%d (actually %s%d)}",
+             base()->representation().Mnemonic(), base()->id(),
+             base()->ActualValue()->representation().Mnemonic(), base()->ActualValue()->id());
+    }
+    PrintF(") LENGTH %s%d CHANGE %s\n",
+           length()->representation().Mnemonic(), length()->id(),
+           skip_check() ? "TRUE" : "FALSE");
+    }
+
+  } else {
+    if (index()->IsRelationTrue(NumericRelation::Ge(),
+                                block()->graph()->GetConstant0()) &&
+        index()->IsRelationTrue(NumericRelation::Lt(), length())) {
+      set_skip_check(true);
+    }
   }
 }
 
 
 bool HBoundsCheck::IsRelationTrueInternal(NumericRelation relation,
-                                          HValue* related_value) {
+                                          HValue* related_value,
+                                          int offset,
+                                          int scale) {
   if (related_value == length()) {
     // A HBoundsCheck is smaller than the length it compared against.
-    return NumericRelation::Lt().Implies(relation);
+    return NumericRelation::Lt().CompoundImplies(relation, 0, 0, offset, scale);
   } else if (related_value == block()->graph()->GetConstant0()) {
     // A HBoundsCheck is greater than or equal to zero.
-    return NumericRelation::Ge().Implies(relation);
+    return NumericRelation::Ge().CompoundImplies(relation, 0, 0, offset, scale);
   } else {
     return false;
   }
@@ -914,6 +1204,15 @@ void HBoundsCheck::PrintDataTo(StringStream* stream) {
   index()->PrintNameTo(stream);
   stream->Add(" ");
   length()->PrintNameTo(stream);
+  if (base() != NULL && (offset() != 0 || scale() != 0)) {
+    stream->Add("base: ((");

[Jakob Kummerow, 2013/03/11 11:55:02]

nit: you probably want to print a space first, i.e. Add(" base: ...

+    if (base() != index()) {
+      index()->PrintNameTo(stream);
+    } else {
+      stream->Add("index");
+    }
+    stream->Add(" + %d) >> %d)", offset(), scale());
+  }
   if (skip_check()) {
     stream->Add(" [DISABLED]");
   }
@@ -941,6 +1240,33 @@ void HBoundsCheck::InferRepresentation(HInferRepresentation* h_infer) {
 }
 
 
+bool HBoundsCheckBaseIndexInformation::IsRelationTrueInternal(
+    NumericRelation relation,
+    HValue* related_value,
+    int offset,
+    int scale) {
+  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);
+}
+
+
 void HCallConstantFunction::PrintDataTo(StringStream* stream) {
   if (IsApplyFunction()) {
     stream->Add("optimized apply ");
@@ -1604,7 +1930,8 @@ void HPhi::AddInformativeDefinitions() {
 }
 
 
-bool HPhi::IsRelationTrueInternal(NumericRelation relation, HValue* other) {
+bool HPhi::IsRelationTrueInternal(
+    NumericRelation relation, HValue* other, int offset, int scale) {

[Jakob Kummerow, 2013/03/11 11:55:02]

for method/function declarations (as opposed to calls), please put every
argument on its own line (unless everything, including the method name, fits
onto a single line).

   if (CheckFlag(kNumericConstraintEvaluationInProgress)) return false;
 
   SetFlag(kNumericConstraintEvaluationInProgress);
@@ -1613,7 +1940,7 @@ bool HPhi::IsRelationTrueInternal(NumericRelation relation, HValue* other) {
     // Skip OSR entry blocks
     if (OperandAt(i)->block()->is_osr_entry()) continue;
 
-    if (!OperandAt(i)->IsRelationTrue(relation, other)) {
+    if (!OperandAt(i)->IsRelationTrue(relation, other, offset, scale)) {
       result = false;
       break;
     }