894813 - IonMonkey: Add a shell flag to check range analysis

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Jan de Mooij [:jandem]]

Jesse's fuzzer found a lot of range analysis problems after I landed bug 864400. That bug seems to have turned them into hardware exceptions.

We can find more bugs and find them faster if we add a new flag (or builtin function) to the shell, like --ion-check-range-analysis=on. When this flag is set, after every instruction that has a range, we emit a new MIR instruction that just checks the value is in the calculated range and if it's not it can masm.callWithABI a function that always asserts.

Bonus points if we can make the assertion include the name of the MIR instruction with the invalid range.

I think it's best to do this only if a special flag is set rather than in all debug builds, to avoid slowing down the code too much and (more important I think) avoid different register allocation in debug vs opt builds etc.

Anybody interested in taking this?

Comment 1

[Dan Gohman [:sunfish]]

Attachment: a rough sketch

Here's a sketch for dynamic range checks, along with hack fixes for what appear to be 3 real bugs that it found. It's missing several possible checks, and the checks it's doing may not be entirely correct, but it does pass tests and jit-tests --tbpl.

I don't know when I'll get back to this, so anyone feel free to pick up the patch and/or work on proper fixes for the bugs it turned up (see the comments in RangeAnalysis.cpp in the patch for details) in the meantime.

Comment 2

[Nicolas B. Pierron [:nbp]]

Comment on attachment 785550 [details] [diff] [review]
a rough sketch

Review of attachment 785550 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/ion/RangeAnalysis.cpp
@@ +1053,5 @@
> +    // --ion-eager. Figure out the right way to cause the result to wrap
> +    // properly when the type is Int32. Also, MAdd and other operators probably
> +    // need similar fixes.
> +    if (type() == MIRType_Int32 && !range()->isInt32())
> +        setRange(new Range());

nit: use range()->wrapAroundToInt32().

::: js/src/ion/RangeAnalysis.h
@@ +176,5 @@
>      {
> +        JS_ASSERT(h == INT64_MIN ?
> +                      (e == MaxDoubleExponent) : (mozilla::FloorLog2(mozilla::Abs(h)) <= e));
> +        JS_ASSERT(l == INT64_MIN ?
> +                      (e == MaxDoubleExponent) : (mozilla::FloorLog2(mozilla::Abs(l)) <= e));

The exponent is supposed to be an over-approximation when we are above the int32 range, so in theory we can compute a larger exponent than the int64/double boundaries.  Just that it can no longer be represented on a double.

I don't think any of the linear operators that we handle can produce a result which reach INT64_MIN or INT64_MAX.

Comment 3

[Dan Gohman [:sunfish]]

Attachment: range-check.patch

Here's a new version of the patch, which is still incomplete. I ported it to top of tree, added a commandline flag, improved the NaN checking, and added a fix for another bug it found.

I am resuming work on this patch now.

Comment 4

[Dan Gohman [:sunfish]]

Attachment: range-check.patch

Ok. This patch is now ready for a more serious review. It contains the new commandline option --ion-check-range-analysis=on (which defaults to off), the range checking code, and fixes for several bugs (all in RangeAnalysis.cpp).

Comment 5

[Nicolas B. Pierron [:nbp]]

Comment on attachment 791031 [details] [diff] [review]
range-check.patch

Review of attachment 791031 [details] [diff] [review]:
-----------------------------------------------------------------

Nice work, still some comments to be addressed.

::: js/src/jit/CodeGenerator.cpp
@@ +7339,5 @@
> +        masm.breakpoint();
> +        masm.bind(&success);
> +    }
> +
> +    // TODO: If r->isDecimal() is true, check it.

I think we do not care much about this case, as it is not used for optimizing, but mostly for deoptimizing, and if we want to make use it later for using float instead of double then we would probably want more information too.

::: js/src/jit/Ion.h
@@ +80,5 @@
> +    // Whether to enable extra code to perform dynamic validation of
> +    // RangeAnalysis results.
> +    //
> +    // Default: false
> +    bool checkRangeAnalysis; 

nit: trailing white space.

::: js/src/jit/LIR-Common.h
@@ +4967,5 @@
> +  public:
> +    LIR_HEADER(RangeAssert)
> +
> +    
> +    LRangeAssert(const LAllocation &input, Range r)

nit: trailing whitespace above.

@@ +4990,5 @@
> +  public:
> +    LIR_HEADER(DoubleRangeAssert)
> +
> +    
> +    LDoubleRangeAssert(const LAllocation &input, const LDefinition &temp, Range r)

nit: trailing whitespace above.

::: js/src/jit/RangeAnalysis.cpp
@@ +1682,5 @@
> +        return true;
> +      case MIRType_Int32:
> +        JS_ASSERT(specialization_ == MIRType_Int32);
> +        if (range() && !range()->isInt32()) {
> +            range()->wrapAroundToInt32();

Actually, the range of a truncated Add can be outside the Int32 range, even if it is specialized as an Int32 add.
returning false below will cause a compilation failure.  We just want to do the same thing as the double case.

@@ +1690,5 @@
> +      default:
> +        break;
> +    }
> +        
> +    return false;

nit: trailing whitespace in MAdd::truncate().

@@ +1709,5 @@
> +        return true;
> +      case MIRType_Int32:
> +        JS_ASSERT(specialization_ == MIRType_Int32);
> +        if (range() && !range()->isInt32()) {
> +            range()->wrapAroundToInt32();

same comment here.

@@ +1717,5 @@
> +      default:
> +        break;
> +    }
> +        
> +    return false;

same nit here.

@@ +1743,5 @@
> +        return true;
> +      case MIRType_Int32:
> +        JS_ASSERT(specialization_ == MIRType_Int32);
> +        if (range() && !range()->isInt32()) {
> +            range()->wrapAroundToInt32();

And same comment here.

::: js/src/jit/RangeAnalysis.h
@@ +176,5 @@
>      {
> +        JS_ASSERT(h == INT64_MIN ?
> +                      (e == MaxDoubleExponent) : (mozilla::FloorLog2(mozilla::Abs(h)) <= e));
> +        JS_ASSERT(l == INT64_MIN ?
> +                      (e == MaxDoubleExponent) : (mozilla::FloorLog2(mozilla::Abs(l)) <= e));

FloorLog2 does not work with 0 and the exponent is an over approximation, so e might be larger than MaxDoubleExponent.

Comment 6

[Jan de Mooij [:jandem]]

Thanks for working on this!

It would be swell if we could run "--ion-eager --ion-check-range-analysis" as part of jit_test.py --tbpl, see the "if options.tbpl:" in jit_test.py

When we removed JM, we removed at least 5 flag combinations from that list, adding one back shouldn't be a problem.

Comment 7

[Dan Gohman [:sunfish]]

This patch is broken as of 1b16c2c729b: "Ensure no instructions are inserted between an instruction and its OsiPoint." It's not clear whether the patch's current approach to inserting instructions can be made to work under this constraint.

Comment 8

[Jan de Mooij [:jandem]]

(In reply to Dan Gohman [:sunfish] from comment #7)
> This patch is broken as of 1b16c2c729b: "Ensure no instructions are inserted
> between an instruction and its OsiPoint." It's not clear whether the patch's
> current approach to inserting instructions can be made to work under this
> constraint.

I think all you need to do is move your code in LIRGenerator::visitInstruction to the end of the function, so that the instruction gets added after the LOsiPoint.

Comment 9

[Dan Gohman [:sunfish]]

(In reply to Jan de Mooij [:jandem] from comment #8)
> I think all you need to do is move your code in
> LIRGenerator::visitInstruction to the end of the function, so that the
> instruction gets added after the LOsiPoint.

Looks like that works!

(In reply to Nicolas B. Pierron [:nbp] from comment #5)
> ::: js/src/jit/RangeAnalysis.h
> @@ +176,5 @@
> >      {
> > +        JS_ASSERT(h == INT64_MIN ?
> > +                      (e == MaxDoubleExponent) : (mozilla::FloorLog2(mozilla::Abs(h)) <= e));
> > +        JS_ASSERT(l == INT64_MIN ?
> > +                      (e == MaxDoubleExponent) : (mozilla::FloorLog2(mozilla::Abs(l)) <= e));
> 
> FloorLog2 does not work with 0 and the exponent is an over approximation, so
> e might be larger than MaxDoubleExponent.

mozilla::FloorLog2 is documented to return 0 on 0. I'll fix the == to be a >=.

Comment 10

[Dan Gohman [:sunfish]]

Attachment: range-check.patch

This update addresses review comments, renames the flag from --ion-check-range-analysis=on to just --ion-check-range-analysis, and moves the code insertion after the LOsiPoint.

Comment 11

[Nicolas B. Pierron [:nbp]]

Comment on attachment 791393 [details] [diff] [review]
range-check.patch

Review of attachment 791393 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit/CodeGenerator.cpp
@@ +7372,5 @@
> +        masm.breakpoint();
> +        masm.bind(&success);
> +    }
> +
> +    // TODO: If r->isDecimal() is true, check it.

Every TODO should have a bug number referenced by the code.  So if you want to keep it, open a bug and index it in the code.

Comment 12

[Dan Gohman [:sunfish]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/f08e4a699011

Comment 13

[Douglas Crosher [:dougc]]

It appears that the range checks are inserted well after the range analysis stage, during lowering to LIR, and at this point the range information has already degraded?  If so then might it be possible to rework the code to insert MIR ops, that check the ranges, while within the scope of the range analysis stage?  Perhaps this could occur as the beta nodes are being removed.

Comment 14

[Dan Gohman [:sunfish]]

(In reply to Douglas Crosher [:dougc] from comment #13)
> It appears that the range checks are inserted well after the range analysis
> stage, during lowering to LIR, and at this point the range information has
> already degraded?  If so then might it be possible to rework the code to
> insert MIR ops, that check the ranges, while within the scope of the range
> analysis stage?  Perhaps this could occur as the beta nodes are being
> removed.

This sounds plausible. It would probably be straightforward to add MRangeAssert and MDoubleRangeAssert instructions which could lower to the LRangeAssert and LDoubleRangeAssert that are there now.

On the other hand, how important is this? It would seem that knowledge of an instruction's range is useful in simplifying the instruction's users, but not so much the instruction itself, so the most interesting instructions should usually still be around at lowering time. Do you see it differently?

Comment 15

[Dan Gohman [:sunfish]]

I temporarily disabled the asserts that were added to Range's constructor since they were triggering on content/canvas/test/test_canvas.html. I'll investigate.

Comment 16

[Nicolas B. Pierron [:nbp]]

(In reply to Douglas Crosher [:dougc] from comment #13)
> It appears that the range checks are inserted well after the range analysis
> stage, during lowering to LIR, and at this point the range information has
> already degraded?

What do you mean by degraded?  The ranges are refined, but we also truncate the result of the operations.  I guess we could disable any optimizations based on range analysis, aka truncate.

The reason why I suggested that ranges should not be used by other instructions than the current one is that we remove extra truncation operations, and used to make assumptions based on the operands, which was wrong.  Adding guards based on the range of one instruction is fine.  Still, this does not account for removed instruction, but this should be ok.

I think this patch is enough, and we do not need for the MIR instructions.

Comment 17

[Douglas Crosher [:dougc]]

(In reply to Dan Gohman [:sunfish] from comment #14)
...
> On the other hand, how important is this? It would seem that knowledge of an
> instruction's range is useful in simplifying the instruction's users, but
> not so much the instruction itself, so the most interesting instructions
> should usually still be around at lowering time. Do you see it differently?

The patch seems very useful as it is. It's not clear to me how important it might be to also reliably check the ranges on inputs.  For example to check that an operation optimized and limited to a uint31 argument actually receives a uint31 input.  It is also not clear how easy it would be to replace the beta nodes with a type check.

Comment 18

[Douglas Crosher [:dougc]]

(In reply to Nicolas B. Pierron [:nbp] from comment #16)
> (In reply to Douglas Crosher [:dougc] from comment #13)
> > It appears that the range checks are inserted well after the range analysis
> > stage, during lowering to LIR, and at this point the range information has
> > already degraded?
> 
> What do you mean by degraded?  The ranges are refined, but we also truncate
> the result of the operations.  I guess we could disable any optimizations
> based on range analysis, aka truncate.

The removal of the beta nodes at the end of range analysis destroys much of the range information, and the remnants are further degraded by other optimizations.  Users of the range information would want to run within the scope of the range analysis stage.  For example if there are more efficient backend instruction sequences for limited ranges of inputs then the choice would be better make within the range analysis stage and perhaps flagged in the MIR object for use when lowering or code generation.  It may well be best to just discard the range information after range analysis to save memory as it has little use.  There does not appear to be any need to disable optimizations, as the type system should be able to work with them.

Comment 19

[Phil Ringnalda (:philor)]

https://hg.mozilla.org/mozilla-central/rev/f08e4a699011
https://hg.mozilla.org/mozilla-central/rev/77bcbb164b45
https://hg.mozilla.org/mozilla-central/rev/efa786fa5f04
https://hg.mozilla.org/mozilla-central/rev/8df3548041d5

Comment 20

[Nicolas B. Pierron [:nbp]]

(In reply to Douglas Crosher [:dougc] from comment #18)
> (In reply to Nicolas B. Pierron [:nbp] from comment #16)
> > (In reply to Douglas Crosher [:dougc] from comment #13)
> > > It appears that the range checks are inserted well after the range analysis
> > > stage, during lowering to LIR, and at this point the range information has
> > > already degraded?
> > 
> > What do you mean by degraded?  The ranges are refined, but we also truncate
> > the result of the operations.  I guess we could disable any optimizations
> > based on range analysis, aka truncate.
> 
> The removal of the beta nodes at the end of range analysis destroys much of
> the range information, and the remnants are further degraded by other
> optimizations.

The removal of the beta nobes should not change the value of the RangeAnalysis, otherwise there is a but in the computeRange functions.  The beta nobes are there as a temporary solution that we do not even need to keep during optimizations working on range analysis, but only during the computeRange functions.

If the range is modified after the computeRange function, usually this is to refine it as we truncate them in the truncate operations.

> For example if there are more efficient
> backend instruction sequences for limited ranges of inputs then the choice
> would be better make within the range analysis stage and perhaps flagged in
> the MIR object for use when lowering or code generation.

As we currently do, but this does not invalidate the range of the current MIR definition.

> It may well be
> best to just discard the range information after range analysis to save
> memory

This won't change a thing, as the Ranges are TempObjects attached to MDefinition.  And so we sould not free space from the LifoAlloc, but we will certainly increase the MIR size to collect every bit that we used to get from the ranges.

Comment 21

[Dan Gohman [:sunfish]]

Attachment: jit-test-tbpl-range-checks.patch

This patch adds an --ion-eager --ion-check-range-analysis to jit_test.py's --tbpl run. The main range check patch fixed all the bugs I observed when running this.

Comment 22

[Dan Gohman [:sunfish]]

Attachment: reinstate the asserts

The asserts were detecting the fact that Range::intersect would construct an invalid Range before testing whether the range would be valid. This patch moves the check so that it's done before creating a Range. And, it re-enables the asserts.

Comment 23

[Nicolas B. Pierron [:nbp]]

Comment on attachment 791744 [details] [diff] [review]
reinstate the asserts

Review of attachment 791744 [details] [diff] [review]:
-----------------------------------------------------------------

Nice catch!

Comment 24

[Jan de Mooij [:jandem]]

Comment on attachment 791742 [details] [diff] [review]
jit-test-tbpl-range-checks.patch

Review of attachment 791742 [details] [diff] [review]:
-----------------------------------------------------------------

Cool.

Comment 25

[Dan Gohman [:sunfish]]

http://hg.mozilla.org/integration/mozilla-inbound/rev/5d0292c05c91
http://hg.mozilla.org/integration/mozilla-inbound/rev/e4a0c6fd1aa9

Comment 26

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/5d0292c05c91
https://hg.mozilla.org/mozilla-central/rev/e4a0c6fd1aa9

Comment 27

[Hannes Verschore [:h4writer]]

Comment on attachment 791742 [details] [diff] [review]
jit-test-tbpl-range-checks.patch

Review of attachment 791742 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit-test/jit_test.py
@@ +143,5 @@
>          # Running all bits would take forever. Instead, we test a few interesting combinations.
>          flags = [
>              [], # no flags, normal baseline and ion
>              ['--ion-eager'], # implies --baseline-eager
> +            ['--ion-eager', '--ion-check-range-analysis'],

Can we add this check to "python jit-tests/jit-tests --ion" too. Since this catches ion issues, I think that makes sense?