DFG CFA should leave behind information in Edge that says if the Edge's type check is proven to succeed

[Filip Pizlo]

It's only sound to DCE an operation if the type checks that will be performed on it are proven to succeed.  Let's consider two examples.

Example #1:

function foo(a, b, c) {
    var x = a + b + c;
}

For simplicity let's assume that argument type checking isn't happening. This transforms to the following DFG IR, if a, b, c are predicted int:

1: GetLocal(arg1)
2: GetLocal(arg2)
3: ValueAdd(Int32:@1, Int32:@2)
4: GetLocal(arg3)
5: ValueAdd(Int32:@3, Int32:@4)

@5 is dead only if the inputs are really numbers, and the rest of the graph is only dead because @5 is dead, and only if the inputs to @3 are also numbers. But if any of the inputs were not numbers, then we could get strangeness: the ValueAdd's could cause valueOf methods to be called, and those methods could have side-effects.

Hence a sound DCE of this code would lead to:

1: GetLocal(arg1)
2: GetLocal(arg2)
3: ValueAdd(Int32:@1, Int32:@2)
4: GetLocal(arg3)
5: Phantom(Int32:@3, Int32:@4)

This is because @5's behavior is dependent on what @3 returns, and @4 is not yet proven to be an int32.  Type check hoisting here could save us; we could instead do:

1: GetLocal(arg1)
2: GetLocal(arg2)
3: GetLocal(arg3)
4: Phantom(Int32:@1, Int32:@2, Int32:@3)

And have @4 exit to the bytecode index associated with 'a + b'.

Broadly speaking, any dead operation that has any children that require type checking needs to keep all of its children alive, and needs to be transformed into a Phantom (with checking edges) on all of its children.

With type check hoisting on arguments enabled (which is true in the DFG right now), we could get more efficient code: we know that both ValueAdd's must operate on Int32's - there are no other types that will flow in. This is the purpose of the bug: have the CFA tell us that the children are already checked. This is a flow-sensitive property and so is a property of the edge, not the node. Consider that the CFA could tell us that edges are already checked; we would get:

1: GetLocal(arg1)
2: GetLocal(arg2)
3: ValueAdd(Proved:Int32:@1, Proved:Int32:@2)
4: GetLocal(arg3)
5: ValueAdd(Proved:Int32:@3, Proved:Int32:@4)

At this point we know that we can simply kill the whole graph, since nothing can have side-effects.

One tricky caveat: @3 could return a double, if not for the overflow check. Of course, returning a double will not affect @5's effectfulness. It will be interesting to come up with a way of handling this.

Example #2:

Consider the code:

function foo(a, b) {
    return [a, b] - 5;
}

In this case, [] will have valueOf called on it, which will involve some sort of prototype chain walk. In general, we cannot guarantee what valueOf will do. It will probably do things to the contents of the array.

This code will transform to:

1: GetLocal(arg1)
2: GetLocal(arg2)
3: NewArray(@1, @2)
4: JSConstant(Int32:5)
5: ArithSub(@3, @4)

In this case, @5 is dead, but its deadness is predicated on the input types not being objects. ArithSub should, in this case, speculate int, since the inputs are not double and the DFG doesn't handle object subtraction. We will get:

1: GetLocal(arg1)
2: GetLocal(arg2)
3: NewArray(@1, @2)
4: JSConstant(Int32:5)
5: ArithSub(NotChecked:Int32:@3, Checked:Int32:@4)

Notice that @3 is not checked at @5, since the CFA will not have been able to prove that @3 is an int (since it isn't one). This means that the best that the DCE could do is:

1: GetLocal(arg1)
2: GetLocal(arg2)
3: NewArray(@1, @2)
4: JSConstant(Int32:5)
5: Phantom(NotChecked:Int32:@3, Checked:Int32:@4)

[Filip Pizlo]

This all makes me think that DCE over conditionally-pure things may not be worth it.

Live would be much easier if we just continued saying that ArithAdd/Sub/Mul/Div are not DCE-able, period.

[Filip Pizlo]

Nah.  This feels way too complicated.  I will come back to this later, and probably do it some other way.

In particular, I just tested to see what would happen if I turned off basically all DCE.  Nothing happened.  Nothing got slower.  It's not worth it to over think this, at least not until some real-world test needs it.

[Filip Pizlo]

I think I do in fact need this.

The crucial bits are:

- Unless we want to do a really complex static analysis we should use NodeMustGenerate on any node that does non-type-check speculation checks that guard the type they return (like an overflow check in an arith node).

- We need to be able to kill nodes that do type checks, and nodes whose result may flow into a type check - but the latter is only safe if the type check is proven successful.  Hence we need CFA to tell us if the type check is proven to succeed.

[Filip Pizlo]

Created attachment 190580 [details]
the patch

[Mark Hahnenberg]

Comment on attachment 190580 [details]
the patch

r=me

[Filip Pizlo]

Landed in http://trac.webkit.org/changeset/144340