Improved range analysis for bitwise operations.

Improved range analysis for bitwise operations.

R=fschneider@chromium.org, verwaest@chromium.org

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

[sra1, 2012-01-09 20:43:24]

If there is interest in going forward with this, I would move BitRange to a
header file (maybe data-flow.h) and add test/test-bitrange.cc

[Sven Panne, 2012-01-10 08:57:52]

I have a general remark about the approach in this CL: If I read the patch
correctly, we lose a lot of information when we convert the BitRange back to a
Range. This happens e.g. when several bitops are chained, which is probably not
an uncommon pattern.

I think the right approach would be that the computed range contains both
extreme values *and* the known bits/bit values, so the necessary information can
be carried between several operations. Note that memory consumption for the
additional fields could be a problem, but we'll have to measure that instead of
doing wild guesses.

A related, but separate problem would be a better handling of loops in the range
analysis, which we should probably handle first to see the real impact of a
better per-instruction range analysis.

So in a nutshell: I like the general idea of the CL, but it things should
probably be done in a different place.

[sra1, 2012-01-14 10:35:39]

On 2012/01/10 08:57:52, Sven wrote:
> I have a general remark about the approach in this CL: If I read the patch
> correctly, we lose a lot of information when we convert the BitRange back to a
> Range. This happens e.g. when several bitops are chained, which is probably
not
> an uncommon pattern.

How much this matters depends on how the information is used.  Current use is
range checking against the Smi range.  For this, the biggest loss of information
is not going from BitRange->Range, but going from Range->BitRange.
BitRange->Range loses information on 'interior' bits, but often that does not
affect whether the range is Smi.

> 
> I think the right approach would be that the computed range contains both
> extreme values *and* the known bits/bit values, so the necessary information
can
> be carried between several operations. Note that memory consumption for the
> additional fields could be a problem, but we'll have to measure that instead
of
> doing wild guesses.

If you write such an analysis you will want to know if the analysis provides
sufficient optimization opportunities to be worth the extra memory, cpu and
development effort.
It is not clear to me how you would make that judgement that the new analysis is
better without improving the current range analysis to overcome the weakness of
the bitwise transfer function.

If you were to move forward with my suggestion, you would be in a good position
to do 'good science'.  With my suggestion, *all* of the range transfer functions
achieve copy propagation and constant folding.  It would no longer be the case
that the analysis produces terrible results just because a variable is used like
a named constant.  The current transfer function on

  var a = 6, b = 10, c = a|b, d = a&b, e = a^b;

estimates c = [0, 15], d = [0, 7], e = [-2^31,2^31-1] where it should really be
c = [14, 14], d = [2, 2], e = [12, 12].

My motivation is the hash function http://jsperf.com/hashcode-string-x/2 (b29)
that has three unnecessary overflow checks.
These persist even if I do manual constant folding (we are using that version in
the core libraries for Dart).

> 
> A related, but separate problem would be a better handling of loops in the
range
> analysis, which we should probably handle first to see the real impact of a
> better per-instruction range analysis.

Yes! Please do that first.
Would that be sufficient to remove the redundant bound check?

We still need a better XOR transfer function to eliminate the overflow check at
the first addition in the loop of the hash function and the first addition after
the loop.

> 
> So in a nutshell: I like the general idea of the CL, but it things should
> probably be done in a different place.

[fschneider, 2012-02-28 13:26:52]

I'd also like to have a cctest for the new BitRange class. Otherwise LGTM.

https://chromiumcodereview.appspot.com/9156001/diff/2002/src/hydrogen-instruc...
File src/hydrogen-instructions.cc (right):

https://chromiumcodereview.appspot.com/9156001/diff/2002/src/hydrogen-instruc...
src/hydrogen-instructions.cc:1317: result.ExtendRange(&lower, &upper);
I'd simplify this by propagating the inputs kMaxInt and kMinInt into ExtendRange
and change it to return a Range object directy:

return result.ExtendRange();

[Sven Panne, 2012-02-28 13:51:27]

Hmmm, I still doubt that chained bitops are handled by this CL, so it has
probably a very restricted use. Shouldn't this be generalized as I suggested?

[sra1, 2013-06-11 05:19:15]

Added test.

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

https://codereview.chromium.org/9156001/diff/2002/src/hydrogen-instructions.c...
src/hydrogen-instructions.cc:1317: result.ExtendRange(&lower, &upper);
On 2012/02/28 13:26:52, fschneider wrote:
> I'd simplify this by propagating the inputs kMaxInt and kMinInt into
ExtendRange
> and change it to return a Range object directy:
> 
> return result.ExtendRange();

This looks a little strange but let me explain.

The code above is the 1x1 decomposition.
Each input range is 'decomposed' into 1 BitRange.
It is possible to do a more precise decompostion into several BitRanges.
2 BitRanges might be the sweet-spot since it prevents change-of-sign polluting
the result.
E.g.  [-2,3] = {xxxxxxxx} as one BitRange, but is {1111111x, 000000xx} as two.

If you have a 2x2 decomposition, then you have 4 intermediate results.

[-2,3] ^ [-1,5] = {xxxxxxxx} ^ {xxxxxxxx} = xxxxxxxx

but 

[-2,3] ^ [-1,5] = {1111111x, 000000xx} ^ {11111111,00000xxx}
  result11 = 1111111x ^ 11111111 = 0000000x
  result12 = 1111111x ^ 00000xxx = 11111xxx
  result21 = 000000xx ^ 11111111 = 111111xx
  result22 = 000000xx ^ 00000xxx = 00000xxx

These can be accumulated into a range as follows:

  result11.ExtendRange(&lower, &upper);  // 0, 1
  result12.ExtendRange(&lower, &upper);  // -8, 1
  result21.ExtendRange(&lower, &upper);  // -8, 1
  result22.ExtendRange(&lower, &upper);  // -8, 7
= [-8,7]

Do you think I should implement the 2x2 decomposition? It is more complex but
does ensure that small signed integers are known to be smi.

[Toon Verwaest, 2013-06-11 09:37:08]

2x2 decomposition sounds better to me, especially given that our range analysis
for a large part is used to avoid overflow checks when smi-tagging.

[fschneider, 2013-06-11 10:22:36]

Still LGTM.

I think it's a good idea to land the 1x1 decomposition to make progress since it
already improves the range analysis for all binary bitwise ops.

As Stephen explained, it can be further extended, but I'd prefer this as a
separate change.

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

https://codereview.chromium.org/9156001/diff/2002/src/hydrogen-instructions.c...
src/hydrogen-instructions.cc:1317: result.ExtendRange(&lower, &upper);
On 2013/06/11 05:19:15, sra1 wrote:
> On 2012/02/28 13:26:52, fschneider wrote:
> > I'd simplify this by propagating the inputs kMaxInt and kMinInt into
> ExtendRange
> > and change it to return a Range object directy:
> > 
> > return result.ExtendRange();
> 
> This looks a little strange but let me explain.
> 
> The code above is the 1x1 decomposition.
> Each input range is 'decomposed' into 1 BitRange.
> It is possible to do a more precise decompostion into several BitRanges.
> 2 BitRanges might be the sweet-spot since it prevents change-of-sign polluting
> the result.
> E.g.  [-2,3] = {xxxxxxxx} as one BitRange, but is {1111111x, 000000xx} as two.
> 
> If you have a 2x2 decomposition, then you have 4 intermediate results.
> 
> [-2,3] ^ [-1,5] = {xxxxxxxx} ^ {xxxxxxxx} = xxxxxxxx
> 
> but 
> 
> [-2,3] ^ [-1,5] = {1111111x, 000000xx} ^ {11111111,00000xxx}
>   result11 = 1111111x ^ 11111111 = 0000000x
>   result12 = 1111111x ^ 00000xxx = 11111xxx
>   result21 = 000000xx ^ 11111111 = 111111xx
>   result22 = 000000xx ^ 00000xxx = 00000xxx
> 
> These can be accumulated into a range as follows:
> 
>   result11.ExtendRange(&lower, &upper);  // 0, 1
>   result12.ExtendRange(&lower, &upper);  // -8, 1
>   result21.ExtendRange(&lower, &upper);  // -8, 1
>   result22.ExtendRange(&lower, &upper);  // -8, 7
> = [-8,7]
> 
> Do you think I should implement the 2x2 decomposition? It is more complex but
> does ensure that small signed integers are known to be smi.

Thanks for the explanation. The code just looked strange to me for the 1x1 case.
It makes sense for the 2x2 case to write it this way.

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

https://codereview.chromium.org/9156001/diff/22003/src/hydrogen-instructions....
src/hydrogen-instructions.cc:2387: */
Remove commented code.

https://codereview.chromium.org/9156001/diff/22003/test/cctest/test-bitrange.cc
File test/cctest/test-bitrange.cc (right):

https://codereview.chromium.org/9156001/diff/22003/test/cctest/test-bitrange....
test/cctest/test-bitrange.cc:1: // Copyright 2010 the V8 project authors. All
rights reserved.
2013

https://codereview.chromium.org/9156001/diff/22003/test/cctest/test-bitrange....
test/cctest/test-bitrange.cc:176: CheckOp(0, 99,  4, 4, &BitRange::Or,  4, 127);
Add a test for xor as well, e.g. 00xx ^ 0100 => 01xx

[Toon Verwaest, 2013-06-11 12:47:46]

Ok, sounds good to me. lgtm as well, with a nit.

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

https://codereview.chromium.org/9156001/diff/22003/src/hydrogen-instructions....
src/hydrogen-instructions.cc:2391: if (left()->range() != NULL)
if (left()->HasRange()) {
...
}

[sra1, 2013-06-12 00:12:23]

I have updated the tests and addressed CR comments.

I don't think I have a password for v8.googlecode.com
Can one of the reviewers commit the change?

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

https://codereview.chromium.org/9156001/diff/22003/src/hydrogen-instructions....
src/hydrogen-instructions.cc:2387: */
On 2013/06/11 10:22:37, fschneider wrote:
> Remove commented code.

Done.

https://codereview.chromium.org/9156001/diff/22003/src/hydrogen-instructions....
src/hydrogen-instructions.cc:2391: if (left()->range() != NULL)
On 2013/06/11 12:47:46, Toon Verwaest wrote:
> if (left()->HasRange()) {
> ...
> }

Done.

https://codereview.chromium.org/9156001/diff/22003/test/cctest/test-bitrange.cc
File test/cctest/test-bitrange.cc (right):

https://codereview.chromium.org/9156001/diff/22003/test/cctest/test-bitrange....
test/cctest/test-bitrange.cc:1: // Copyright 2010 the V8 project authors. All
rights reserved.
On 2013/06/11 10:22:37, fschneider wrote:
> 2013

Done.

[Toon Verwaest, 2013-06-14 16:55:42]

Committed patchset #6 manually as r15170 (presubmit successful).

[Toon Verwaest, 2013-06-14 17:24:15]

The test file breaks on Windows, so I reverted.