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

Handling expression decomposition and array bounds check hoisting: working code with lots of debugging PrintFs, postdominance check still missing.

Committed: https://code.google.com/p/v8/source/detail?r=13961

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

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.cc
File src/hydrogen-instructions.cc (right):

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.cc#...
src/hydrogen-instructions.cc:195: // Try to satisfy the lower bound on this
value
better comment:
// Check if we already know that this value satisfies the lower bound.

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.cc#...
src/hydrogen-instructions.cc:207: // Try to satisfy the upper bound on this
value
better comment:
// Check if we already know that this value satisfies the upper bound.

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.cc#...
src/hydrogen-instructions.cc:230: // See if the constraints can be satisfied by
decomposition.
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.

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.cc#...
src/hydrogen-instructions.cc:262: HValue* value, HValue* upper)
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).

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.cc#...
src/hydrogen-instructions.cc:268: offset_(0), scale_(0) {
let's give each initializer its own line.

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.cc#...
src/hydrogen-instructions.cc:272: HValue*
HValue::RangeEvaluationContext::ConvertGuarantee(HValue* guarantee) {
This method is simple enough to live in the .h file (if you want).

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.cc#...
src/hydrogen-instructions.cc:1034: if (context->origin()->ActualValue() ==
base()->ActualValue() &&
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;
  }

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.cc#...
src/hydrogen-instructions.cc:1038: change_direction_ = 1;
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.)

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.cc#...
src/hydrogen-instructions.cc:1049: if (offset() < context->offset()) {
Since this condition doesn't have an else-branch, you can fold it into the
previous condition ("... && offset_ < context->offset()").

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.cc#...
src/hydrogen-instructions.cc:1059: change_direction_ = 1;
To make it more obvious that this is closely related to index_can_increase(),
I'd introduce a setter function set_index_must_increase().

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.cc#...
src/hydrogen-instructions.cc:1085: if (HasOriginalIndex() || skip_check())
return;
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.

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.cc#...
src/hydrogen-instructions.cc:1087: HValue* base_index = NULL;
I think you mean index_base, index_offset, index_scale here.

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.cc#...
src/hydrogen-instructions.cc:1132: base_ = NULL;
Is it necessary to do this cleanup?

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.cc#...
src/hydrogen-instructions.cc:1151: if (index()->TryGuaranteeRange(length())) {
This should *not* be inside the if(FLAG_log_abcd) block!

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.cc#...
src/hydrogen-instructions.cc:1208: stream->Add("base: ((");
nit: you probably want to print a space first, i.e. Add(" base: ...

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.cc#...
src/hydrogen-instructions.cc:1934: NumericRelation relation, HValue* other, int
offset, int scale) {
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).

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.h
File src/hydrogen-instructions.h (right):

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:673: bool CompoundOperandsAreCompatible(int
my_offset,
I don't like this name. "compatible" in what sense? How about "ComponentsImply"
instead?
Also, this should be private.

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:679: case EQ: return my_offset == other_offset &&
my_scale == other_scale;
let's combine identical cases, i.e.:

    switch (kind_) {
      case EQ:
      case NE: return my_offset == other_offset && my_scale == other_scale;
      case GT:
      case GE: return my_offset <= other_offset && my_scale >= other_scale;
      case LT:
      case LE: return my_offset >= other_offset && my_scale <= other_scale;
      case NONE: break;  // Fall through to UNREACHABLE().
    }

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:690: // CompoundOperandsAreCompatible returns true
when
comment is about the wrong method.

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:1029: bool IsRelationTrue(
This method is big enough to move its implementation to the .cc file.

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:1030: NumericRelation relation, HValue* other, int
offset = 0, int scale = 0) {
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).

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:1032: return
NumericRelation::Eq().Implies(relation);
Doesn't this need updating to account for offset/scale?

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:1041: -offset)) return true;
if-statements that span multiple lines need {}. I'd format like this:
    if (scale == 0 &&
        other->IsRelationTrueInternal(relation.Reversed(), this, -offset)) {
      return true;
    }

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:1068: class RangeEvaluationContext BASE_EMBEDDED {
I'd prefer this to be a top-level class.

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:1078: bool lower_check_satisfied() { return
lower_check_guarantee_ != NULL; }
I'd prefer not to have this method, because it adds confusion to call sites:
it's not obvious that set_lower_check_guarantee(...) changes the return value of
lower_check_satisfied(). You can s/lower_check_guarantee/lower_check/, and then
just inline this: "if (lower_check() == NULL) { /*...*/; set_lower_check(...);
}"

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:1080: bool RangeSatisfied() {
is_range_satisfied()

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:1091: template <class T> void swap(T& a, T& b) {
Private helper function should be private (or global in utils.h).
Also, please use pointers for arguments that are modified:
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Refere...

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:1092: T c(a); a=b; b=c;
nit: formatting: one statement per line, spaces around '='.

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:1095: void swap_origin(HValue*& other_origin,
Again, all references must be const. Use pointers.

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:1103: RangeEvaluationContext(HValue* value, HValue*
upper);
nit: constructor should be before methods
(http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Declar...)

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:1104: private:
nit: empty line before "private:"

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:1109: HValue* origin_;
I'm not too happy with the name "origin_", it's bit too generic. Ideas:
"provable_", "candidate_", "value_in_question_".

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:1188: // relation they provide on the redefined
value.
Please extend this comment:
// Returns true if it is guaranteed that:
// ((this + offset) >> scale) relation other

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:1189: virtual bool
IsRelationTrueInternal(NumericRelation relation, HValue* other,
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).

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:3096: virtual bool IsRelationTrueInternal(
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).

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:3527: friend class HBoundsCheckBaseIndexInformation;
Friend declarations should always be in the "private:" section
(http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Declar...).

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:3538: : key_mode_(key_mode), skip_check_(false),
let's put each initializer onto its own line.

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:3565: ASSERT(base() == NULL);
nit: You're using accessors ("base()") and direct member access ("base_")
alternatingly. I would prefer consistency. I don't feel strongly about which
version you choose; personally I'd go with direct member access because there's
no need to use accessors for a class's own members, and because it's consistent
with stores (where you're not using setters).

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:3635: HBoundsCheckBaseIndexInformation(HBoundsCheck*
check) {
explicit

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

I replied only to the comments where I disagree or where I did something
different.
I *think* that I have addressed everything else...

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.cc
File src/hydrogen-instructions.cc (right):

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.cc#...
src/hydrogen-instructions.cc:230: // See if the constraints can be satisfied by
decomposition.
On 2013/03/11 11:55:02, Jakob wrote:
> Why does this need to happen in the recursive call (and therefore possibly
> several times)?

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.

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.cc#...
src/hydrogen-instructions.cc:272: HValue*
HValue::RangeEvaluationContext::ConvertGuarantee(HValue* guarantee) {
On 2013/03/11 11:55:02, Jakob wrote:
> This method is simple enough to live in the .h file (if you want).

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

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.cc#...
src/hydrogen-instructions.cc:1132: base_ = NULL;
On 2013/03/11 11:55:02, Jakob wrote:
> Is it necessary to do this cleanup?

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

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.h
File src/hydrogen-instructions.h (right):

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:1032: return
NumericRelation::Eq().Implies(relation);
On 2013/03/11 11:55:02, Jakob wrote:
> Doesn't this need updating to account for offset/scale?

No, this is a real identity check, if "this" and "other" are the same then they
are equal, and if being equal implies the required relation we return true.

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:1078: bool lower_check_satisfied() { return
lower_check_guarantee_ != NULL; }
On 2013/03/11 11:55:02, Jakob wrote:
> I'd prefer not to have this method, because it adds confusion to call sites:
> it's not obvious that set_lower_check_guarantee(...) changes the return value
of
> lower_check_satisfied(). You can s/lower_check_guarantee/lower_check/, and
then
> just inline this: "if (lower_check() == NULL) { /*...*/; set_lower_check(...);
> }"

I ended up renaming the methods, and at this point I think the code is more
readable with the helpers instead of having NULL pointers checks inlined.

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

Looking pretty good now.

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.cc
File src/hydrogen-instructions.cc (right):

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.cc#...
src/hydrogen-instructions.cc:230: // See if the constraints can be satisfied by
decomposition.
On 2013/03/13 15:58:14, Massi wrote:
> On 2013/03/11 11:55:02, Jakob wrote:
> > Why does this need to happen in the recursive call (and therefore possibly
> > several times)?
> 
> 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.

OK, I see.

https://codereview.chromium.org/12377072/diff/1/src/hydrogen-instructions.cc#...
src/hydrogen-instructions.cc:1132: base_ = NULL;
On 2013/03/13 15:58:14, Massi wrote:
> On 2013/03/11 11:55:02, Jakob wrote:
> > Is it necessary to do this cleanup?
> 
> In principle, no, but I don't like leaving meaningless values around...

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.

https://codereview.chromium.org/12377072/diff/5001/src/flag-definitions.h
File src/flag-definitions.h (right):

https://codereview.chromium.org/12377072/diff/5001/src/flag-definitions.h#new...
src/flag-definitions.h:134: DEFINE_bool(new_abcd, true, "use new abcd")
Please move this next to FLAG_idefs. You could also rename it to
idef_based_abce.
As discussed offline, at some point we should combine those two flags, but that
can wait.

https://codereview.chromium.org/12377072/diff/5001/src/hydrogen-instructions.cc
File src/hydrogen-instructions.cc (right):

https://codereview.chromium.org/12377072/diff/5001/src/hydrogen-instructions....
src/hydrogen-instructions.cc:176: // If scale is 0 try the reversed relation..
nit: s/.././

https://codereview.chromium.org/12377072/diff/5001/src/hydrogen-instructions.h
File src/hydrogen-instructions.h (right):

https://codereview.chromium.org/12377072/diff/5001/src/hydrogen-instructions....
src/hydrogen-instructions.h:691: case NONE: return false;
As an additional safeguard, I'd prefer:
case NONE: break;  // Fall through to UNREACHABLE().

https://codereview.chromium.org/12377072/diff/5001/src/hydrogen-instructions....
src/hydrogen-instructions.h:721: bool is_lower_bound_satisfied() { return
lower_check_guarantee_ != NULL; }
I'm still not quite happy with these names.
(1) What's a "check guarantee"? I think it would make more sense to call it
either "lower_check_" or "lower_bound_guarantee_".
(2) This method right here is very similar to a getter. Its name should match
the variable that's being looked at:
bool has_foo() { return foo_ != NULL; }
(I still think it would be fine to just inline the NULL checks, but if you
prefer explicit methods that's OK too.)

https://codereview.chromium.org/12377072/diff/5001/src/hydrogen-instructions....
src/hydrogen-instructions.h:1082: DIRECTION_BOTH = 4
Looks like you're not using DIRECTION_BOTH anywhere, but if you were, you'd
probably want DIRECTION_BOTH == DIRECTION_LOWER | DIRECTION_UPPER, so it must be
3.

https://codereview.chromium.org/12377072/diff/5001/src/hydrogen-instructions....
src/hydrogen-instructions.h:3492: friend class HBoundsCheckBaseIndexInformation;
Friend declarations should always be in the "private:" section
(http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Declar...)

https://codereview.chromium.org/12377072/diff/5001/src/hydrogen-instructions....
src/hydrogen-instructions.h:4491: if (!scale != 0) return false;
I think you mean s/!scale/*scale/.

Please add a test case that would have caught this.

[Massi, 2013-03-14 15:07:18]

https://codereview.chromium.org/12377072/diff/5001/src/flag-definitions.h
File src/flag-definitions.h (right):

https://codereview.chromium.org/12377072/diff/5001/src/flag-definitions.h#new...
src/flag-definitions.h:134: DEFINE_bool(new_abcd, true, "use new abcd")
On 2013/03/14 12:50:09, Jakob wrote:
> Please move this next to FLAG_idefs. You could also rename it to
> idef_based_abce.
> As discussed offline, at some point we should combine those two flags, but
that
> can wait.

Done.

https://codereview.chromium.org/12377072/diff/5001/src/hydrogen-instructions.cc
File src/hydrogen-instructions.cc (right):

https://codereview.chromium.org/12377072/diff/5001/src/hydrogen-instructions....
src/hydrogen-instructions.cc:176: // If scale is 0 try the reversed relation..
On 2013/03/14 12:50:09, Jakob wrote:
> nit: s/.././

Done.

https://codereview.chromium.org/12377072/diff/5001/src/hydrogen-instructions.h
File src/hydrogen-instructions.h (right):

https://codereview.chromium.org/12377072/diff/5001/src/hydrogen-instructions....
src/hydrogen-instructions.h:691: case NONE: return false;
On 2013/03/14 12:50:09, Jakob wrote:
> As an additional safeguard, I'd prefer:
> case NONE: break;  // Fall through to UNREACHABLE().

Done.

https://codereview.chromium.org/12377072/diff/5001/src/hydrogen-instructions....
src/hydrogen-instructions.h:721: bool is_lower_bound_satisfied() { return
lower_check_guarantee_ != NULL; }
On 2013/03/14 12:50:09, Jakob wrote:
> I'm still not quite happy with these names.
> (1) What's a "check guarantee"? I think it would make more sense to call it
> either "lower_check_" or "lower_bound_guarantee_".
> (2) This method right here is very similar to a getter. Its name should match
> the variable that's being looked at:
> bool has_foo() { return foo_ != NULL; }
> (I still think it would be fine to just inline the NULL checks, but if you
> prefer explicit methods that's OK too.)

Done.

https://codereview.chromium.org/12377072/diff/5001/src/hydrogen-instructions....
src/hydrogen-instructions.h:1082: DIRECTION_BOTH = 4
On 2013/03/14 12:50:09, Jakob wrote:
> Looks like you're not using DIRECTION_BOTH anywhere, but if you were, you'd
> probably want DIRECTION_BOTH == DIRECTION_LOWER | DIRECTION_UPPER, so it must
be
> 3.

Done.

https://codereview.chromium.org/12377072/diff/5001/src/hydrogen-instructions....
src/hydrogen-instructions.h:3492: friend class HBoundsCheckBaseIndexInformation;
On 2013/03/14 12:50:09, Jakob wrote:
> Friend declarations should always be in the "private:" section
>
(http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Declar...)

Done (in the "protected:" section).

https://codereview.chromium.org/12377072/diff/5001/src/hydrogen-instructions....
src/hydrogen-instructions.h:4491: if (!scale != 0) return false;
On 2013/03/14 12:50:09, Jakob wrote:
> I think you mean s/!scale/*scale/.
> 
> Please add a test case that would have caught this.

Done, but with a small refactoring.

[Jakob Kummerow, 2013-03-14 16:16:32]

I like this refactoring!

LGTM with a few more nits.

https://codereview.chromium.org/12377072/diff/17001/src/flag-definitions.h
File src/flag-definitions.h (right):

https://codereview.chromium.org/12377072/diff/17001/src/flag-definitions.h#ne...
src/flag-definitions.h:210: DEFINE_bool(idefs, true, "use informative
definitions")
We're not turning this on yet by default, are we? Please don't forget to undo
this change before landing.

https://codereview.chromium.org/12377072/diff/17001/src/hydrogen-instructions.h
File src/hydrogen-instructions.h (right):

https://codereview.chromium.org/12377072/diff/17001/src/hydrogen-instructions...
src/hydrogen-instructions.h:717: bool Apply(HValue* b, int o, int s = 0) {
nit: please spell out the names ("base", "offset", "scale")

https://codereview.chromium.org/12377072/diff/17001/src/hydrogen-instructions...
src/hydrogen-instructions.h:718: if (base() == NULL) {
nit: s/base()/base_/ [for consistency with "base_ = b" and "if (scale_ == 0)"]

There are more places below where the same comment applies.

https://codereview.chromium.org/12377072/diff/17001/src/hydrogen-instructions...
src/hydrogen-instructions.h:735: void SwapValues(HValue** b, int* o, int* s) {
again

https://codereview.chromium.org/12377072/diff/17001/src/hydrogen-instructions...
src/hydrogen-instructions.h:1115: DIRECTION_BOTH =
DIRECTION_UPPER|DIRECTION_LOWER
nit: spaces around '|'

https://codereview.chromium.org/12377072/diff/17001/src/hydrogen-instructions...
src/hydrogen-instructions.h:4516: virtual bool TryDecompose(DecompositionResult*
decomposition) {
Shouldn't we make the same change to HShr too?

https://codereview.chromium.org/12377072/diff/17001/src/hydrogen-instructions...
src/hydrogen-instructions.h:4520: // like ((base = offset) >> scale) with one
single decomposition.
nit: s/=/+/

[Jakob Kummerow, 2013-03-14 16:18:16]

one more nit

https://codereview.chromium.org/12377072/diff/17001/test/mjsunit/array-bounds...
File test/mjsunit/array-bounds-check-removal.js (right):

https://codereview.chromium.org/12377072/diff/17001/test/mjsunit/array-bounds...
test/mjsunit/array-bounds-check-removal.js:221: if (false) {
debugging leftover?

[Massi, 2013-03-18 08:06:14]

Committed manually as r13961 (presubmit successful).