Precise shift right result type derivation for all int32 input ranges.

Precise shift right result type derivation for all int32 input ranges.

The typer can do better for the shift right operation, and can compute
the result range precisely and very simply in one line of code for
each limit. The patch also canonicalizes the shift range which gives a
precise result range for all int32 shift ranges.

BUG=

[dougc, 2015-05-04 01:36:04]

dtc-v8@scieneer.com changed reviewers:
+ titzer@chromium.org

[titzer, 2015-05-06 11:53:13]

The logic looks good. I think we need to start splitting out some of this logic
into more testable pieces.

https://codereview.chromium.org/1121573004/diff/1/src/compiler/typer.cc
File src/compiler/typer.cc (right):

https://codereview.chromium.org/1121573004/diff/1/src/compiler/typer.cc#newco...
src/compiler/typer.cc:993: int32_t shift_min = rhs->Min();
Would it be possible to pull the integer range logic out to a separate function
so that it can be tested simple integer ranges instead of requiring the
construction of types, etc? That would allow more exhaustive and more efficient
unit testing, and allow us to apply the rules to machine-left shifts, too.

[dougc, 2015-05-13 07:43:03]

On 2015/05/06 11:53:13, titzer wrote:
...
> Would it be possible to pull the integer range logic out to a separate
function
> so that it can be tested simple integer ranges instead of requiring the
> construction of types, etc? That would allow more exhaustive and more
efficient
> unit testing, and allow us to apply the rules to machine-left shifts, too.

Yes this sounds good and improved testing performance. Note the test is still
slow - more testing has been added. The test takes around 5 seconds here. If you
can give me a realistic time then testing can be scaled to fit?

Also it was not clear how best to split this out. A new IntType was added which
just has the int32_t limits for now, but might be extended with alignment or
known ones and zeros in future. If you could help get this patch through then
I'll update the other patches to use the same style.

ptal.

[Sven Panne, 2015-05-18 12:10:17]

On 2015/05/13 07:43:03, dougc wrote:
> [...] Yes this sounds good and improved testing performance. Note the test is
still
> slow - more testing has been added. The test takes around 5 seconds here. If
you
> can give me a realistic time then testing can be scaled to fit? [...]

5 seconds are roughly 2 orders of magnitude to big: If every test we run during
"make -j32 qc" took that long, it would roughly take 3.5 hours. So the rule of
thumb is that a unit test should take a few dozen ms at most. Of course there is
a tension between good test coverage and testing time, but more exhaustive tests
should be split off into something separate (we discussed this several times
already, but I'm not sure what the current state of this is).

What you could do for unit testing is: Generate some sane fixed number (e.g.
1000) of pseudo-random inputs to the function you want to test and check only
those, probably for various "interesting" range combinations. This is e.g. the
idea behind Haskell's QuickCheck
(https://hackage.haskell.org/package/QuickCheck), and there are some C++ ports
of this which might be worth considering, this kind of testing problem comes up
again and again.

[titzer, 2015-05-19 08:47:30]

On 2015/05/18 12:10:17, Sven Panne wrote:
> On 2015/05/13 07:43:03, dougc wrote:
> > [...] Yes this sounds good and improved testing performance. Note the test
is
> still
> > slow - more testing has been added. The test takes around 5 seconds here. If
> you
> > can give me a realistic time then testing can be scaled to fit? [...]
> 
> 5 seconds are roughly 2 orders of magnitude to big: If every test we run
during
> "make -j32 qc" took that long, it would roughly take 3.5 hours. So the rule of
> thumb is that a unit test should take a few dozen ms at most. Of course there
is
> a tension between good test coverage and testing time, but more exhaustive
tests
> should be split off into something separate (we discussed this several times
> already, but I'm not sure what the current state of this is).
> 

Yes, 5 seconds is a bit too long. If you run the test runner with --time, it
will output a list of the longest running tests. You don't want to make this
list :-) Under 100ms would be acceptable.


> What you could do for unit testing is: Generate some sane fixed number (e.g.
> 1000) of pseudo-random inputs to the function you want to test and check only
> those, probably for various "interesting" range combinations. This is e.g. the
> idea behind Haskell's QuickCheck
> (https://hackage.haskell.org/package/QuickCheck), and there are some C++ ports
> of this which might be worth considering, this kind of testing problem comes
up
> again and again.

Boundary cases and some systematic tests within reasonable limits would be fine.
Please don't add pseudo-random tests without a fixed seed; we have that in the
typer tests and then they fail nondeterministically--even if they catch a bug,
it may be several CLs too late.

[titzer, 2016-03-10 10:12:28]

titzer@chromium.org changed reviewers:
- titzer@chromium.org