Simple array bounds check elimination on top of range analysis framework.

Simple array bounds check elimination on top of range analysis framework.

Currenly eliminates only bounds checks when there is an implicit constraint bounding index's range with array length.

Does not eliminate redundancy in expressions like a[i + 1], a[i].

R=fschneider@google.com
BUG=

Committed: https://code.google.com/p/dart/source/detail?r=14141

[srdjan, 2012-10-25 20:51:36]

DBC

https://codereview.chromium.org/11262033/diff/1/runtime/vm/intermediate_langu...
File runtime/vm/intermediate_language.cc (right):

https://codereview.chromium.org/11262033/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.cc:2169: 
Remove one empty line

https://codereview.chromium.org/11262033/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.cc:2229: }
Remove the code above

https://codereview.chromium.org/11262033/diff/1/runtime/vm/intermediate_langu...
File runtime/vm/intermediate_language.h (right):

https://codereview.chromium.org/11262033/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.h:1629: bool IsSymbol() const { return kind_ ==
kSymbol; }
IsSymbol  is a pretty widely used operation on class String. I would use a
different name to make it more readable ( reading the call sites, I thought we
were dealing with Strings). Ditto for IsConstant.

[Florian Schneider, 2012-10-26 11:10:07]

LGTM.

https://codereview.chromium.org/11262033/diff/1/runtime/vm/intermediate_langu...
File runtime/vm/intermediate_language.cc (right):

https://codereview.chromium.org/11262033/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.cc:2112: a.symbol()->Equals(b.symbol());
I think !a->AffecteedBySideEffect() &&a->Equals(b) implies
!b->AffecteedBySideEffect().

https://codereview.chromium.org/11262033/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.cc:2332: Range::ConstantMax(constraint()));
Indentation.

https://codereview.chromium.org/11262033/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.cc:2392: *result =
RangeBoundary::FromDefinition(a.symbol(), a.offset() - b.value());
Guard against smi-overflow here.

https://codereview.chromium.org/11262033/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.cc:2405: *result =
RangeBoundary::FromDefinition(a.symbol(), a.offset() + b.value());
Guard against overflow here, so that the result offset is always a smi.

https://codereview.chromium.org/11262033/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.cc:2410: *result =
RangeBoundary::FromDefinition(b.symbol(), b.offset() + a.value());
Guard against smi-overflow here as well.

https://codereview.chromium.org/11262033/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.cc:2429: left_defn->IsLoadField() ?
Does this need to be for every LoadField, or only array-length LoadField?

https://codereview.chromium.org/11262033/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.cc:2434:
RangeBoundary::FromDefinition(left_defn) : left_range->max();
Maybe add a TODO to support the case where right()->definition() is a LoadField.

Should we have a canonicalization of commutative smi-ops like + and * so that if
there is a constant operand, there is always one on the right side?

[Florian Schneider, 2012-10-26 11:12:28]

Please also add a command line flag to control array bounds check elimination.

On 2012/10/26 11:10:07, Florian Schneider wrote:
> LGTM.
> 
>
https://codereview.chromium.org/11262033/diff/1/runtime/vm/intermediate_langu...
> File runtime/vm/intermediate_language.cc (right):
> 
>
https://codereview.chromium.org/11262033/diff/1/runtime/vm/intermediate_langu...
> runtime/vm/intermediate_language.cc:2112: a.symbol()->Equals(b.symbol());
> I think !a->AffecteedBySideEffect() &&a->Equals(b) implies
> !b->AffecteedBySideEffect().
> 
>
https://codereview.chromium.org/11262033/diff/1/runtime/vm/intermediate_langu...
> runtime/vm/intermediate_language.cc:2332: Range::ConstantMax(constraint()));
> Indentation.
> 
>
https://codereview.chromium.org/11262033/diff/1/runtime/vm/intermediate_langu...
> runtime/vm/intermediate_language.cc:2392: *result =
> RangeBoundary::FromDefinition(a.symbol(), a.offset() - b.value());
> Guard against smi-overflow here.
> 
>
https://codereview.chromium.org/11262033/diff/1/runtime/vm/intermediate_langu...
> runtime/vm/intermediate_language.cc:2405: *result =
> RangeBoundary::FromDefinition(a.symbol(), a.offset() + b.value());
> Guard against overflow here, so that the result offset is always a smi.
> 
>
https://codereview.chromium.org/11262033/diff/1/runtime/vm/intermediate_langu...
> runtime/vm/intermediate_language.cc:2410: *result =
> RangeBoundary::FromDefinition(b.symbol(), b.offset() + a.value());
> Guard against smi-overflow here as well.
> 
>
https://codereview.chromium.org/11262033/diff/1/runtime/vm/intermediate_langu...
> runtime/vm/intermediate_language.cc:2429: left_defn->IsLoadField() ?
> Does this need to be for every LoadField, or only array-length LoadField?
> 
>
https://codereview.chromium.org/11262033/diff/1/runtime/vm/intermediate_langu...
> runtime/vm/intermediate_language.cc:2434:
> RangeBoundary::FromDefinition(left_defn) : left_range->max();
> Maybe add a TODO to support the case where right()->definition() is a
LoadField.
> 
> Should we have a canonicalization of commutative smi-ops like + and * so that
if
> there is a constant operand, there is always one on the right side?

[Vyacheslav Egorov (Google), 2012-10-26 14:23:29]

Thanks for the review. Landing.

https://codereview.chromium.org/11262033/diff/1/runtime/vm/intermediate_langu...
File runtime/vm/intermediate_language.cc (right):

https://codereview.chromium.org/11262033/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.cc:2112: a.symbol()->Equals(b.symbol());
On 2012/10/26 11:10:07, Florian Schneider wrote:
> I think !a->AffecteedBySideEffect() &&a->Equals(b) implies
> !b->AffecteedBySideEffect().

Done.

https://codereview.chromium.org/11262033/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.cc:2169: 
On 2012/10/25 20:51:36, srdjan wrote:
> Remove one empty line

Done.

https://codereview.chromium.org/11262033/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.cc:2229: }
On 2012/10/25 20:51:36, srdjan wrote:
> Remove the code above

Done.

https://codereview.chromium.org/11262033/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.cc:2332: Range::ConstantMax(constraint()));
On 2012/10/26 11:10:07, Florian Schneider wrote:
> Indentation.

Done.

https://codereview.chromium.org/11262033/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.cc:2392: *result =
RangeBoundary::FromDefinition(a.symbol(), a.offset() - b.value());
On 2012/10/26 11:10:07, Florian Schneider wrote:
> Guard against smi-overflow here.

Done.

https://codereview.chromium.org/11262033/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.cc:2405: *result =
RangeBoundary::FromDefinition(a.symbol(), a.offset() + b.value());
On 2012/10/26 11:10:07, Florian Schneider wrote:
> Guard against overflow here, so that the result offset is always a smi.

Done.

https://codereview.chromium.org/11262033/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.cc:2410: *result =
RangeBoundary::FromDefinition(b.symbol(), b.offset() + a.value());
On 2012/10/26 11:10:07, Florian Schneider wrote:
> Guard against smi-overflow here as well.

Done.

https://codereview.chromium.org/11262033/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.cc:2429: left_defn->IsLoadField() ?
On 2012/10/26 11:10:07, Florian Schneider wrote:
> Does this need to be for every LoadField, or only array-length LoadField?

Narrowed symbolic computation to length.

https://codereview.chromium.org/11262033/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.cc:2434:
RangeBoundary::FromDefinition(left_defn) : left_range->max();
On 2012/10/26 11:10:07, Florian Schneider wrote:
> Maybe add a TODO to support the case where right()->definition() is a
LoadField.
> 
> Should we have a canonicalization of commutative smi-ops like + and * so that
if
> there is a constant operand, there is always one on the right side?

Done.

https://codereview.chromium.org/11262033/diff/1/runtime/vm/intermediate_langu...
File runtime/vm/intermediate_language.h (right):

https://codereview.chromium.org/11262033/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.h:1629: bool IsSymbol() const { return kind_ ==
kSymbol; }
On 2012/10/25 20:51:36, srdjan wrote:
> IsSymbol  is a pretty widely used operation on class String. I would use a
> different name to make it more readable ( reading the call sites, I thought we
> were dealing with Strings). Ditto for IsConstant.

I am not sure how to rename it. I agree that it is unfortunate that symbol and
constant have a lot of different meanings. However it is used in a very limited
scope (range analysis) where it has a well defined meaning, just like "symbolic
computations" have a well defined meaning that has nothing to do with strings.

I am open to suggestions and will rename if we manage to come up with something
that is recognizable.