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

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 142 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));
   }
 }
 
 
+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;
     return kMaxInt;
   }
   if (result < kMinInt) {
     *overflow = true;
     return kMinInt;
   }
   return static_cast<int32_t>(result);
@@ skipping 602 matching lines @@
     if (other_operand == NULL) continue;
     HBasicBlock* other_block = other_operand->block();
     if (cur_block == other_block) {
       if (!other_operand->IsPhi()) {
         HInstruction* cur = this->previous();
         while (cur != NULL) {
           if (cur == other_operand) break;
           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 {
       // If the following assert fires, you may have forgotten an
       // AddInstruction.
       ASSERT(other_block->Dominates(cur_block));
     }
   }
 
   // Verify that instructions that may have side-effects are followed
@@ skipping 83 matching lines @@
 
 void HBinaryCall::PrintDataTo(StringStream* stream) {
   first()->PrintNameTo(stream);
   stream->Add(" ");
   second()->PrintNameTo(stream);
   stream->Add(" ");
   stream->Add("#%d", argument_count());
 }
 
 
+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;
   }
 }
 
 
 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]");
   }
 }
 
 
 void HBoundsCheck::InferRepresentation(HInferRepresentation* h_infer) {
   ASSERT(CheckFlag(kFlexibleRepresentation));
   Representation r;
   if (key_mode_ == DONT_ALLOW_SMI_KEY ||
       !length()->representation().IsTagged()) {
     r = Representation::Integer32();
   } else if (index()->representation().IsTagged() ||
       (index()->ActualValue()->IsConstant() &&
        HConstant::cast(index()->ActualValue())->HasSmiValue())) {
     // If the index is tagged, or a constant that holds a Smi, allow the length
     // to be tagged, since it is usually already tagged from loading it out of
     // the length field of a JSArray. This allows for direct comparison without
     // untagging.
     r = Representation::Tagged();
   } else {
     r = Representation::Integer32();
   }
   UpdateRepresentation(r, h_infer, "boundscheck");
 }
 
 
+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 ");
   } else {
     stream->Add("%o ", function()->shared()->DebugName());
   }
   stream->Add("#%d", argument_count());
 }
 
 
@@ skipping 643 matching lines @@
           HInductionVariableAnnotation::AddToGraph(this,
                                                    relations[relation_index],
                                                    other_operand_index);
         }
       }
     }
   }
 }
 
 
-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);
   bool result = true;
   for (int i = 0; i < OperandCount(); i++) {
     // 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;
     }
   }
   ClearFlag(kNumericConstraintEvaluationInProgress);
 
   return result;
 }
 
 
@@ skipping 1473 matching lines @@
 
 
 void HCheckFunction::Verify() {
   HInstruction::Verify();
   ASSERT(HasNoUses());
 }
 
 #endif
 
 } }  // namespace v8::internal