The WebKit blog article gave a good overview of the analysis passes. However, since static analyses are hueristic algorithms, the concrete algorithm design is as important as (if not more important than) the high-level idea to yield a working solution. I’m also curious about the other static analysis passes performed by JSC that are not covered in the article.
So I decided to dive into the implementation to get a better understanding of the full picture. This turns out to be much harder than I expected, primarily due to the lack of comments in the codebase. So I’m taking notes here for future reference.
Specialized DFG IR Node Type
The first optimization is not an optimization pass, but happens when the DFG IR is generated from the source-of-truth bytecode. For certain operations, there exists a specialized version of IR node type in addition to the general version. For example,
ValueAdd handles the general addition that makes no assumption on operand types, while
ArithAdd handles the case where both operands are statically known to be numbers (e.g., not
The logic that selects between the two versions can be found here. As one can see from the code, if the IR node types for the two operands both always return
Number result (the IR node type list maintains what each node type may return), then an
ArithAdd is emitted instead of
ValueAdd. Since this is before any analysis or optimizations are run, there isn’t anything fancy here: all it checks is the IR node type.
- I found this diff, which introduced the
ValueSubopcode, quite helpful to understand what’s going on here.
- I wasn’t able to figure out why the criteria for selecting
op1->hasNumberResult() && op2->hasNumberResult(). The
if-check rules out result types that are more precise than
Double), but I can’t see the reason to rule out such cases.
Backward Propagation Pass
Backward propagation is the first static analysis pass executed by the DFG JIT.
The backward propagation pass computes five flags for each DFG IR node. The flags are stored as part of [the
UsesAsNumber: whether the node result may be used in a context that observes fractional, or bigger-than-int32, results.
UsesAsOther: whether the node result may be used in a context that distinguishes between
NeedsNegZero: whether the node result may be used in a context that distinguishes between
UsesAsInt: whether the node result may be used in a context that prefers (but not requires)
UsesAsArrayIndex: whether the node result may be used in a context that strongly prefers
For the first three flags, not setting a flag that ought to be set is a correctness issue.
For example, if the flag
UsesAsOther is not set, but a node
x is actually used in a context that distinguished
x + "123"), then the program may be misoptimized, and the user may observe unexpected result for that computation (e.g., getting
"NaN123" instead of
NeedsNegZero flag seems (based on this bug report) to enable some
-0 related optimizations. For example,
a + (-0) can be optimized to
a by speculating
a to be not
-0. The speculation is usually worth because
-0 is rare, but it’s better to not speculate at all: if
a + (-0) is part of a larger expression, and we can prove that even if
a + (-0) were
-0, the result of the full expression would be the same as if it were
0, then we can omit the speculation. One example where speculation
a != (-0) can be omitted is
(a + (-0)) + 1, and one counterexample where speculation
a != (-0) is required is
1 / (a + (-0)). This is what the flag tries to determine.
int32 and also outputs
int32, so certain overflow checks can be eliminated if the output is fed into a bit-operator (for example, in
(a + 1) | 0, if
a were speculated as an
int32_t, the overflow check for
For the last two flags, however, not setting a flag that ought to be set is merely a performance issue and does not affect correctness.
The motivation for
UseAsArrayIndex flag is that the conversion from a
int is an expensive instruction, and since it is used as array index, it could be inside a loop and cause a big performance impact, so we should avoid this bad case if possible.
In the initial state of a node, all the five flags are not set. The backward propagation pass is executed to set up the five flags (and it must set the first three flags correctly for correctness).
The backward propagation pass is a monotonic process. Each flag may only be switched from
set, but not the other way. This makes sure that a fixed point (where further execution of the pass can result in no state changes) is guaranteed to be eventually reached. However, this also means that if at one point we set a flag which condition actually never happens in reality, there is no way to undo the bad decision.
The pass iterates until the fixpoint is reached. In each iteration, it does the following:
- Iterate each basic block in reverse order.
- Iterate each IR instruction node in the basic block in reverse order.
- For the current IR node, use its flags to update the flags of its operand (i.e., children) nodes. The concrete update logic depends on the node type, and is handwritten.
Since there are close to 400 different IR node types, for correctness, the default operation (for a node type not handled in the switch-case) is conservative: it sets the first three flags in all its operands.
As another conservative measure, even for node types that are explicitly handled, the default flags to propagate is the flags of the current node. So flags are propagated all the way down by default, and only stopped when the logic is explicitly written to not propagate a flag.
We will use the logic for
ValueAdd and the logic for
ArithAdd as examples to illustrate how the algorithm works.
ArithAdd, since we already know the two operands must be
Numbers, it’s safe to not set the
UsesAsOther flag for its operands. And if at least one of the operands is known to be not a
-0, then the result of the add must not be a
-0 as well, so the
-0 in the operand will not be observable after the add, so in this case it’s safe to not set the
NeedsNegZero flag for both operands.
ValueAdd is similar to
ArithAdd, except that it may take non-
Number operands. In that case,
NaN in operand may be distinguished (for example, in
x + "123"). Therefore, for
UsesAsOther flag is only not propagated if at least one of the operand is known to produce numeric results (in that case, if the other side is
NaN, the final result is always the same, so the two are indistinguishable). Note that such criteria is not complete (sufficient but not necessary): but this is as far as static analysis can go.
- I couldn’t fully understand the purpose or implementations of the
UsedAsNumberflag. Any explanations would be welcomed.
- The pass did not handle operators like
ValueMul, etc. It seems to me the developers forgot to update the pass when those operators are introduced.
One interesting thing is about the “conservative” measures implemented in the code to reduce the risk of correctness bugs. If my interpretation that the devs forgot to put
ValueMul, etc. into the pass is correct, then on one hand, the conservative measures indeed prevented a correctness bug. But on the other hand, since no correctness bug is produced, it would take a long time to figure out that the pass has become outdated and has been silently producing suboptimal results.