Add a value range analysis phase to remove bounds checks.

Add a value range analysis phase to remove bounds checks.
Committed: https://code.google.com/p/dart/source/detail?r=12957

[Søren Gjesse, 2012-09-26 09:08:24]

https://codereview.chromium.org/10968060/diff/14/lib/compiler/implementation/...
File lib/compiler/implementation/js_backend/constant_system_javascript.dart
(right):

https://codereview.chromium.org/10968060/diff/14/lib/compiler/implementation/...
lib/compiler/implementation/js_backend/constant_system_javascript.dart:46:
apply(left, right) => dartBitOperation.apply(left, right);
Why do you not need to implement JavaScript semantics here?

https://codereview.chromium.org/10968060/diff/14/lib/compiler/implementation/...
File lib/compiler/implementation/ssa/codegen.dart (right):

https://codereview.chromium.org/10968060/diff/14/lib/compiler/implementation/...
lib/compiler/implementation/ssa/codegen.dart:3: // BSD-style license that can be
found in the LICENSE file.
Maybe add a visitRangeConversion which asserts false.

https://codereview.chromium.org/10968060/diff/14/lib/compiler/implementation/...
File lib/compiler/implementation/ssa/optimize.dart (right):

https://codereview.chromium.org/10968060/diff/14/lib/compiler/implementation/...
lib/compiler/implementation/ssa/optimize.dart:201: HInstruction
visitInvokeInterceptor(HInvokeInterceptor node) {
Add a comment on the pattern recognized here.

https://codereview.chromium.org/10968060/diff/14/lib/compiler/implementation/...
File lib/compiler/implementation/ssa/value_range_analyzer.dart (right):

https://codereview.chromium.org/10968060/diff/14/lib/compiler/implementation/...
lib/compiler/implementation/ssa/value_range_analyzer.dart:89: class MaxValue
extends Value {
Should this maybe be called MaxIntValue and extend IntValue instead (then it
should implement isZero)?

https://codereview.chromium.org/10968060/diff/14/lib/compiler/implementation/...
lib/compiler/implementation/ssa/value_range_analyzer.dart:109: class MinValue
extends Value {
MinIntValue?

https://codereview.chromium.org/10968060/diff/14/lib/compiler/implementation/...
lib/compiler/implementation/ssa/value_range_analyzer.dart:206: Value operator
-(Value other) {
Could you please explain how this works?

https://codereview.chromium.org/10968060/diff/14/lib/compiler/implementation/...
lib/compiler/implementation/ssa/value_range_analyzer.dart:247: Range range = new
Range(lower.min(other.lower), upper.max(other.upper));
Maybe add Range.normalize constructor.

https://codereview.chromium.org/10968060/diff/14/lib/compiler/implementation/...
lib/compiler/implementation/ssa/value_range_analyzer.dart:345: return const
Range(const MinValue(), const MaxValue());
What is the difference between returning null and returning an unbounded range?

https://codereview.chromium.org/10968060/diff/14/lib/compiler/implementation/...
lib/compiler/implementation/ssa/value_range_analyzer.dart:436: }
Missing explicit return.

https://codereview.chromium.org/10968060/diff/14/lib/compiler/implementation/...
lib/compiler/implementation/ssa/value_range_analyzer.dart:551: }
Missing explicit "return null" here.

https://codereview.chromium.org/10968060/diff/14/lib/compiler/implementation/...
lib/compiler/implementation/ssa/value_range_analyzer.dart:572:
assert(phi.inputs.length == 2);
Ditto.

https://codereview.chromium.org/10968060/diff/14/lib/compiler/implementation/...
lib/compiler/implementation/ssa/value_range_analyzer.dart:600: * recognize
updated on the loop phi, we must [unwrap] the [HCheck]
updated -> updates

[ngeoffray, 2012-09-26 09:33:26]

New patchset upladed.

https://codereview.chromium.org/10968060/diff/14/lib/compiler/implementation/...
File lib/compiler/implementation/js_backend/constant_system_javascript.dart
(right):

https://codereview.chromium.org/10968060/diff/14/lib/compiler/implementation/...
lib/compiler/implementation/js_backend/constant_system_javascript.dart:46:
apply(left, right) => dartBitOperation.apply(left, right);
On 2012/09/26 09:08:24, Søren Gjesse wrote:
> Why do you not need to implement JavaScript semantics here?

Because apply is semantic agnostic. It just calls the dart operator on left and
right.

https://codereview.chromium.org/10968060/diff/14/lib/compiler/implementation/...
File lib/compiler/implementation/ssa/codegen.dart (right):

https://codereview.chromium.org/10968060/diff/14/lib/compiler/implementation/...
lib/compiler/implementation/ssa/codegen.dart:3: // BSD-style license that can be
found in the LICENSE file.
On 2012/09/26 09:08:24, Søren Gjesse wrote:
> Maybe add a visitRangeConversion which asserts false.

Done.

https://codereview.chromium.org/10968060/diff/14/lib/compiler/implementation/...
File lib/compiler/implementation/ssa/optimize.dart (right):

https://codereview.chromium.org/10968060/diff/14/lib/compiler/implementation/...
lib/compiler/implementation/ssa/optimize.dart:201: HInstruction
visitInvokeInterceptor(HInvokeInterceptor node) {
On 2012/09/26 09:08:24, Søren Gjesse wrote:
> Add a comment on the pattern recognized here.
> 

Done.

https://codereview.chromium.org/10968060/diff/14/lib/compiler/implementation/...
File lib/compiler/implementation/ssa/value_range_analyzer.dart (right):

https://codereview.chromium.org/10968060/diff/14/lib/compiler/implementation/...
lib/compiler/implementation/ssa/value_range_analyzer.dart:89: class MaxValue
extends Value {
On 2012/09/26 09:08:24, Søren Gjesse wrote:
> Should this maybe be called MaxIntValue and extend IntValue instead (then it
> should implement isZero)?

Renaming is fine, but if it extends IntValue what value would you put in the
[value] field? Also, all values here a re "int" values, so would you prefer if
IntValue was renamed to ConcreteIntValue?

https://codereview.chromium.org/10968060/diff/14/lib/compiler/implementation/...
lib/compiler/implementation/ssa/value_range_analyzer.dart:206: Value operator
-(Value other) {
On 2012/09/26 09:08:24, Søren Gjesse wrote:
> Could you please explain how this works?

Done.

https://codereview.chromium.org/10968060/diff/14/lib/compiler/implementation/...
lib/compiler/implementation/ssa/value_range_analyzer.dart:247: Range range = new
Range(lower.min(other.lower), upper.max(other.upper));
On 2012/09/26 09:08:24, Søren Gjesse wrote:
> Maybe add Range.normalize constructor.

Good point. Done.

https://codereview.chromium.org/10968060/diff/14/lib/compiler/implementation/...
lib/compiler/implementation/ssa/value_range_analyzer.dart:345: return const
Range(const MinValue(), const MaxValue());
On 2012/09/26 09:08:24, Søren Gjesse wrote:
> What is the difference between returning null and returning an unbounded
range?

It's to make sure an instruction that has type int gets a range. See assert line
335. I agree it doesn't look nice, so maybe I could just get rid of that assert
and create a [min,max] range if range is null. WDYT?

https://codereview.chromium.org/10968060/diff/14/lib/compiler/implementation/...
lib/compiler/implementation/ssa/value_range_analyzer.dart:436: }
On 2012/09/26 09:08:24, Søren Gjesse wrote:
> Missing explicit return.

Done.

https://codereview.chromium.org/10968060/diff/14/lib/compiler/implementation/...
lib/compiler/implementation/ssa/value_range_analyzer.dart:551: }
On 2012/09/26 09:08:24, Søren Gjesse wrote:
> Missing explicit "return null" here.

Done.

https://codereview.chromium.org/10968060/diff/14/lib/compiler/implementation/...
lib/compiler/implementation/ssa/value_range_analyzer.dart:572:
assert(phi.inputs.length == 2);
On 2012/09/26 09:08:24, Søren Gjesse wrote:
> Ditto.

Done.

https://codereview.chromium.org/10968060/diff/14/lib/compiler/implementation/...
lib/compiler/implementation/ssa/value_range_analyzer.dart:600: * recognize
updated on the loop phi, we must [unwrap] the [HCheck]
On 2012/09/26 09:08:24, Søren Gjesse wrote:
> updated -> updates

Done.

[Søren Gjesse, 2012-09-26 14:00:15]

lgtm

https://codereview.chromium.org/10968060/diff/14/lib/compiler/implementation/...
File lib/compiler/implementation/ssa/value_range_analyzer.dart (right):

https://codereview.chromium.org/10968060/diff/14/lib/compiler/implementation/...
lib/compiler/implementation/ssa/value_range_analyzer.dart:89: class MaxValue
extends Value {
On 2012/09/26 09:33:26, ngeoffray wrote:
> On 2012/09/26 09:08:24, Søren Gjesse wrote:
> > Should this maybe be called MaxIntValue and extend IntValue instead (then it
> > should implement isZero)?
> 
> Renaming is fine, but if it extends IntValue what value would you put in the
> [value] field? Also, all values here a re "int" values, so would you prefer if
> IntValue was renamed to ConcreteIntValue?

Another alternative is to have AbstractIntValue with subclasses IntValue,
MaxIntValue and MinIntValue. But then AbstractIntValue does not add much.

Thinking about it maybe the comments for MaxValue and MinValue should just be
changed to not mention integer. As far as I can see they could be used with
doubles as well if we where to start tracking double value ranges.

Then IntValue should be abstract then without the value field with

https://codereview.chromium.org/10968060/diff/14/lib/compiler/implementation/...
lib/compiler/implementation/ssa/value_range_analyzer.dart:345: return const
Range(const MinValue(), const MaxValue());
On 2012/09/26 09:33:26, ngeoffray wrote:
> On 2012/09/26 09:08:24, Søren Gjesse wrote:
> > What is the difference between returning null and returning an unbounded
> range?
> 
> It's to make sure an instruction that has type int gets a range. See assert
line
> 335. I agree it doesn't look nice, so maybe I could just get rid of that
assert
> and create a [min,max] range if range is null. WDYT?

I think returning the [min,max] range instead of null will look better. Another
option will be to return null here if the instruction does not have type
integer.

https://codereview.chromium.org/10968060/diff/12001/lib/compiler/implementati...
File lib/compiler/implementation/ssa/codegen.dart (right):

https://codereview.chromium.org/10968060/diff/12001/lib/compiler/implementati...
lib/compiler/implementation/ssa/codegen.dart:1944: }
Maybe assert that not both under and over are null.

https://codereview.chromium.org/10968060/diff/12001/lib/compiler/implementati...
File lib/compiler/implementation/ssa/nodes.dart (right):

https://codereview.chromium.org/10968060/diff/12001/lib/compiler/implementati...
lib/compiler/implementation/ssa/nodes.dart:2578: accept(HVisitor visitor) =>
visitor.visitRangeConversion(this);
Maybe add a comment that we only do range analysis for integers.

https://codereview.chromium.org/10968060/diff/12001/lib/compiler/implementati...
File lib/compiler/implementation/ssa/optimize.dart (right):

https://codereview.chromium.org/10968060/diff/12001/lib/compiler/implementati...
lib/compiler/implementation/ssa/optimize.dart:202: // Try to recognize [:new
List(int):].
Isn't it "Try to recognize length interceptor with input [:new List(int):]"?

https://codereview.chromium.org/10968060/diff/12001/lib/compiler/implementati...
File lib/compiler/implementation/ssa/value_range_analyzer.dart (right):

https://codereview.chromium.org/10968060/diff/12001/lib/compiler/implementati...
lib/compiler/implementation/ssa/value_range_analyzer.dart:115: if
(other.isNegative()) return other;
Shouldn't this be MinValue instead of other? They only have the MSB at an
infinite position in common.

https://codereview.chromium.org/10968060/diff/12001/lib/compiler/implementati...
lib/compiler/implementation/ssa/value_range_analyzer.dart:216: // Will return
IntValue(-42)
So using the fact that (a - b) - c == a - (b - c) == (a - c) - b.

https://codereview.chromium.org/10968060/diff/12001/lib/compiler/implementati...
lib/compiler/implementation/ssa/value_range_analyzer.dart:390: bool
handleBoundsCheck(HBoundsCheck check) {
Maybe comment that this returns true is the bounds check was eliminated.

[Søren Gjesse, 2012-09-26 14:12:24]

One additional comment: How about adding printout of ranges to the tracer?

[ngeoffray, 2012-09-27 09:06:08]

On 2012/09/26 14:12:24, Søren Gjesse wrote:
> One additional comment: How about adding printout of ranges to the tracer?

Ranges are currently specific to the ValueRangeAnalyzer, so the tracer does not
have access to them. I'll think about ways to externalize them

[ngeoffray, 2012-09-27 13:22:02]

Thanks Soren

https://codereview.chromium.org/10968060/diff/14/lib/compiler/implementation/...
File lib/compiler/implementation/ssa/value_range_analyzer.dart (right):

https://codereview.chromium.org/10968060/diff/14/lib/compiler/implementation/...
lib/compiler/implementation/ssa/value_range_analyzer.dart:89: class MaxValue
extends Value {
On 2012/09/26 14:00:15, Søren Gjesse wrote:
> On 2012/09/26 09:33:26, ngeoffray wrote:
> > On 2012/09/26 09:08:24, Søren Gjesse wrote:
> > > Should this maybe be called MaxIntValue and extend IntValue instead (then
it
> > > should implement isZero)?
> > 
> > Renaming is fine, but if it extends IntValue what value would you put in the
> > [value] field? Also, all values here a re "int" values, so would you prefer
if
> > IntValue was renamed to ConcreteIntValue?
> 
> Another alternative is to have AbstractIntValue with subclasses IntValue,
> MaxIntValue and MinIntValue. But then AbstractIntValue does not add much.
> 
> Thinking about it maybe the comments for MaxValue and MinValue should just be
> changed to not mention integer. As far as I can see they could be used with
> doubles as well if we where to start tracking double value ranges.
> 
> Then IntValue should be abstract then without the value field with 

Let's rename MaxValue and MinValue to MaxIntValue and MinIntValue for now. I'd
prefer not to take decisions on what things we might implement in the future.

https://codereview.chromium.org/10968060/diff/12001/lib/compiler/implementati...
File lib/compiler/implementation/ssa/codegen.dart (right):

https://codereview.chromium.org/10968060/diff/12001/lib/compiler/implementati...
lib/compiler/implementation/ssa/codegen.dart:1944: }
On 2012/09/26 14:00:15, Søren Gjesse wrote:
> Maybe assert that not both under and over are null.

Done.

https://codereview.chromium.org/10968060/diff/12001/lib/compiler/implementati...
File lib/compiler/implementation/ssa/nodes.dart (right):

https://codereview.chromium.org/10968060/diff/12001/lib/compiler/implementati...
lib/compiler/implementation/ssa/nodes.dart:2578: accept(HVisitor visitor) =>
visitor.visitRangeConversion(this);
On 2012/09/26 14:00:15, Søren Gjesse wrote:
> Maybe add a comment that we only do range analysis for integers.

Done.

https://codereview.chromium.org/10968060/diff/12001/lib/compiler/implementati...
File lib/compiler/implementation/ssa/optimize.dart (right):

https://codereview.chromium.org/10968060/diff/12001/lib/compiler/implementati...
lib/compiler/implementation/ssa/optimize.dart:202: // Try to recognize [:new
List(int):].
On 2012/09/26 14:00:15, Søren Gjesse wrote:
> Isn't it "Try to recognize length interceptor with input [:new List(int):]"?

Yes, done.

https://codereview.chromium.org/10968060/diff/12001/lib/compiler/implementati...
File lib/compiler/implementation/ssa/value_range_analyzer.dart (right):

https://codereview.chromium.org/10968060/diff/12001/lib/compiler/implementati...
lib/compiler/implementation/ssa/value_range_analyzer.dart:115: if
(other.isNegative()) return other;
On 2012/09/26 14:00:15, Søren Gjesse wrote:
> Shouldn't this be MinValue instead of other? They only have the MSB at an
> infinite position in common.

Good point. Done.

https://codereview.chromium.org/10968060/diff/12001/lib/compiler/implementati...
lib/compiler/implementation/ssa/value_range_analyzer.dart:216: // Will return
IntValue(-42)
On 2012/09/26 14:00:15, Søren Gjesse wrote:
> So using the fact that (a - b) - c == a - (b - c) == (a - c) - b.

Added as a comment.

https://codereview.chromium.org/10968060/diff/12001/lib/compiler/implementati...
lib/compiler/implementation/ssa/value_range_analyzer.dart:390: bool
handleBoundsCheck(HBoundsCheck check) {
On 2012/09/26 14:00:15, Søren Gjesse wrote:
> Maybe comment that this returns true is the bounds check was eliminated.

Done.