[webkit-dev] DFG jit Type checking

[Filip Pizlo]

> I'm trying to figure out how does the DFG JIT type checking work?

In brief: We first predict what the types of expressions will be based on value profiling in both the LLInt and baseline JIT, and then attempt to generate code with the minimal set of type checks needed to ensure soundness.  Type check failures result in OSR exit to baseline JIT code, so after a type check the subsequent code is compiled with a propagated type proof.  Type checks are both hoisted and sunk; we try to place type checks at the first use that requires type information after the assignment to the variable (sinking to first use), except for cases where the live range of the variable crosses basic blocks, in which case the checks are hoisted to the basic blocks that did the assignments (this is a cheap alternative to loop invariant type check motion).  Really simple example:

x = o.f; // no type check for x here, though there may be a type check for o, if it's o's first yse
// ... much of things that are not related to x
y = x; // no type check for x, since the use is type-agnostic
z = x + 6; // check that x is whatever we predicted. for example if the predictions say that x is an int and we know that this expression is unlikely to overflow, we will check that it's an int
w = x - 1; // no type check, since we already checked x.
v = z + 2; // no type check, since we know that z must be an int because it was created by an int binary op that does not overflow.

> I'm also interested in the following: if I start DFG JIT without using LICM will the types of variables be checked in the cycle?

No, type checks are almost always hoisted up to the basic block that assigned the variable.

> To make it clear, I'll bring this example
> for (var j=0; j<10000; j++)
> {
>         var i = 10;
>         var h = j + i;
> }
> How will the type of variable " i " be checked in that example?
> 
"i" will not have any checks, since you set i to 10, which is a constant.

Actually, this program is going to be almost entirely optimized away, since all of the assignments are dead.  Our compiler will not completely kill all of this code yet, since we don't yet have all of the control flow simplification awesomeness that we want. But you might consider a slightly more interesting example, assuming for that "i" is still typically an integer:

var o = p.g; // we will check p's type if it hadn't already been checked, and we will check o's type as well, because its live range crosses basic blocks and this is the last assignment before the end of this basic block
for (var j = 0; j < 10000; ++j) { // no type checks for j, since we know statically that j is an int
    var i = o.f; // we will not check o's type, but we will not hoist o.f out of the loop - both because we don't do full LICM and because the print() statement below may be a side effect.
    var h = j + i; // check i's type. j's type doesn't need to be checked.
    print(h); // load "print" from the global object, check that it's the "print" that we expected, and call it.
}

Hope this helps!

-Filip

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.webkit.org/pipermail/webkit-dev/attachments/20120315/f6af91a1/attachment.html>