1007213 - Range Analysis truncates above type-barriers used by truncated operations.

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, defect)

Description

[Benjamin Bouvier [:bbouvier] (inactive)]

+++ This bug was initially created as a clone of Bug #1006910 +++

As shown in bug 1006910, here is another test case that has the same behavior:

function getval(o) {
    return obj.val
}
function f(x, o) {
    var lhs = -(~x >>> 0)
    var rhs = getval(o)
    return (lhs - rhs >> 0)
}
function getObj(v) {
    return {
        val: v
    }
}

var obj = getObj(1)
assertEq(f(0, obj), 0)
assertEq(f(0, obj), 0)
obj = getObj('can has bug?')
obj = getObj(.5)
assertEq(f(0, obj), 1)


This test case asserts with --ion-eager --ion-parallel-compile=off, on the last line.
What's going on:
- the two first times getval is called, it returns int32, so Ion will assume it returns int32, with a typebarrier.
- in f(), (~x >>> 0) === UINT32_MAX, which doesn't have rounding errors (as it's not fractional), so the multiplication by -1 can be truncated as much as its uses.
- as rhs is an int32 in f(), the subtraction has 2 int32 as inputs and the result is truncated => Range analysis decides to truncate it.
- as a matter of fact, the multiplication (lhs) is truncated.
- on the last line, obj.val isn't an integer anymore, so the call to getval in f will provoke a bailout. The issue is that the multiplication, which is in the resume point, has the int32 type and already has been computed and truncated, so the value on the stack is -1, although it should be -UINT32_MAX.
- kaboom.

nbp helped me making up that test case from bug 1006910, as the test case there can be fixed easily another way (by inlining in Ion the calls to asinh and such -- note that the test case doesn't fail if we replace asinh by asin, as Math.asin is inlined as a MMathFunction, which has the MIR type Double from the beginning, so no doubt is possible).

nbp's solution would be to:
1) implement RMul, the recover instruction for multiplications,
2) use a recoverable copy of the MMul in the resume point rather than the truncated original.
3) (maybe) do the same for all MInstructions that can be truncated.

Comment 1

[Nicolas B. Pierron [:nbp]]

The problem that we see here, is that we have a type barrier which is used to guard what Baseline told us, which is that we only saw one type, as opposed to what can be expected.  The type barrier is made such as we can optimize instructions which are coming after based on the information provided by the barrier.

We can solve this in 2 ways:
 - The easiest, is to prevent any range analysis optimization if one of the inputs used for the computation is uncertain (flow from a type barrier).  This implies that even if we have type information, we are stuck with double math.
 - The complex one, is to make copies of the original operations and uses these in the resume points as long as they are not effectful.  We can restrict this optimization in the context of type-barriers which are flowing in truncated results, as well as remove resume points (where we already skip the RA)

I think we should go for the easiest solution for now, unless it is costly on benchmarks.

Comment 3

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

Guessing :bbouvier is working on this - this blocks differential testing with Math.asinh as per bug 1006910.

Comment 4

[Benjamin Bouvier [:bbouvier] (inactive)]

(In reply to Gary Kwong [:gkw] [:nth10sd] from comment #3)
> Guessing :bbouvier is working on this - this blocks differential testing
> with Math.asinh as per bug 1006910.

I am not actually. I'll try to come back on it soon.

Comment 5

[Nicolas B. Pierron [:nbp]]

Attachment: Recover truncated instructions.

Not asking for review, as this code depend on the fact that we are able to
recover any resume point operand, which means that this implementation
depends on Bug 1062869.

Also, This depends on the implementation of the recover instruction for
MToDouble, which should not be hard to do for number inputs.

Comment 6

[Nicolas B. Pierron [:nbp]]

Attachment: Capture implicit dead branches caused by type barriers.

Comment 7

[Dan Gohman [:sunfish]]

Comment on attachment 8493871 [details] [diff] [review]
Capture implicit dead branches caused by type barriers.

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

LGTM, provided that there aren't any surprises in the answers to my questions :-).

::: js/src/jit/MIRGraph.cpp
@@ +987,5 @@
> +    }
> +
> +    // If none, take the entry resume point.
> +    if (!rp)
> +        rp = entryResumePoint();

Is it possible that there could be no entry resume point at this point?

::: js/src/jit/TypePolicy.cpp
@@ +271,5 @@
>          }
>  
>          MUnbox *unbox = MUnbox::New(alloc, ins->getOperand(0), outputType, MUnbox::TypeBarrier);
>          ins->block()->insertBefore(ins, unbox);
> +        ins->block()->flagOperandsOfPrunedBranches(unbox);

Could you add a comment here briefly explaining what this line is doing? Here's my understanding:

"This unbox dynamically checks that the type matches what we expect. If the checks fail, it triggers a bailout. The bailout code will observe the values before this bailout in ways that the MIR optimizer won't see, so we mark any such values as "UseRemoved" to tell the optimizer that it can't do optimizations on them which depend on seeing all the uses."

Is that right?

Comment 8

[Nicolas B. Pierron [:nbp]]

(In reply to Dan Gohman [:sunfish] from comment #7)
> ::: js/src/jit/MIRGraph.cpp
> @@ +987,5 @@
> > +    }
> > +
> > +    // If none, take the entry resume point.
> > +    if (!rp)
> > +        rp = entryResumePoint();
> 
> Is it possible that there could be no entry resume point at this point?

The only blocks which do not have any entryResumePoint in Ion, are the SplitEdge blocks.  SplitEdge blocks only have a Goto instruction at the time of the Apply Type phase.  In adjustInputs, we are manipulating instructions (ins) which have a TypePolicy.  So, as a Goto has no operand and no type policy, the entry resume point should exists.

So, no, this not possible.  The entry resume point should exists and I will add an assertion after this line.

> ::: js/src/jit/TypePolicy.cpp
> @@ +271,5 @@
> >          }
> >  
> >          MUnbox *unbox = MUnbox::New(alloc, ins->getOperand(0), outputType, MUnbox::TypeBarrier);
> >          ins->block()->insertBefore(ins, unbox);
> > +        ins->block()->flagOperandsOfPrunedBranches(unbox);
> 
> Could you add a comment here briefly explaining what this line is doing?
> Here's my understanding:
> 
> "This unbox dynamically checks that the type matches what we expect. If the
> checks fail, it triggers a bailout. The bailout code will observe the values
> before this bailout in ways that the MIR optimizer won't see, so we mark any
> such values as "UseRemoved" to tell the optimizer that it can't do
> optimizations on them which depend on seeing all the uses."
> 
> Is that right?

This is correct.
I will add a comment.

Comment 9

[Nicolas B. Pierron [:nbp]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/233cb55654a3

Comment 10

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/233cb55654a3

Comment 11

[Hannes Verschore [:h4writer]]

Comment on attachment 8493871 [details] [diff] [review]
Capture implicit dead branches caused by type barriers.

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

::: js/src/jit/TypePolicy.cpp
@@ +271,5 @@
>          }
>  
>          MUnbox *unbox = MUnbox::New(alloc, ins->getOperand(0), outputType, MUnbox::TypeBarrier);
>          ins->block()->insertBefore(ins, unbox);
> +        ins->block()->flagOperandsOfPrunedBranches(unbox);

Like discussed on IRC, this might be in the wrong place. As in: shouldn't all TypeBarriers have this flag, instead of only the TypeBarriers which unbox.

<h4writer> nbp, as I understand "flagOperandsOfPrunedBranches", I think this should be done on any MTypeBarrier
<h4writer> nbp, since if input type is MIRType_Object, the input type can have more objects and the typebarrier pruning a few out of it
<h4writer> nbp, as a result we could inline a property get