Static Analysis in JavaScriptCore (Part I)

Recently I’ve been spending time to understand some internals of JavaScriptCore (JSC), the Javascript JIT compiler powering the Safari browser. For background knowledge, I strongly recommend this great article from WebKit blog for a detailed overview of JSC.

This series of posts attempts to dive deeper into a specific area of JSC: the static analysis passes in JSC’s DFG JIT. Since Javascript is a highly dynamic langauge, it is critical to obtain as much type information as possible to better understand program behaviors so optimizations can take place. In JSC, static analysis is the primary tool for this purpose.

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.

Disclaimer
I do not work on JavaScriptCore, my experience with Javascript is very limited, and I do not have prior experience on static analysis. Everything described in this post is from my understanding of the JSC source code. They may be inaccurate or outright wrong. Please feel free to email me at haoranxu510 [at] gmail.com for any corrections and discussions.

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 String or BigInt or Object).

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.

Side notes:

• I found this diff, which introduced the ValueSub opcode, quite helpful to understand what’s going on here.
• I wasn’t able to figure out why the criteria for selecting ArithAdd is op1->hasNumberResult() && op2->hasNumberResult(). The if-check rules out result types that are more precise than Number (e.g., Int32, Int52 or 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 NodeFlags field]((https://github.com/WebKit/WebKit/blob/8d5e5fd60f0712a47548a3b84c397836c481db75/Source/JavaScriptCore/dfg/DFGNodeFlags.h) in each node. The definitions for the five flags are listed below, as per comments in the code:

• 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 undefined and NaN.
• NeedsNegZero: whether the node result may be used in a context that distinguishes between +0 and -0.
• UsesAsInt: whether the node result may be used in a context that prefers (but not requires) int values.
• UsesAsArrayIndex: whether the node result may be used in a context that strongly prefers int values.

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 undefined and NaN (e.g., x + "123"), then the program may be misoptimized, and the user may observe unexpected result for that computation (e.g., getting "NaN123" instead of "undefined123").

The 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.

The UsedAsNumber flag, based on my guess (from this commit), is designed to enable a special Javascript-specific optimization: Javascript bit-operators cast input to 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 a + 1 may be omitted). It’s pretty tricky as seen from the related code and I can’t fully understand how the logic and optimization works. Given also that it seems to be a Javascript-specific optimization, I will overlook this flag below.

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 double to 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.

The Algorithm

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 unset to 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.

For 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, undefined and NaN in operand may be distinguished (for example, in x + "123"). Therefore, for ValueAdd, the 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 undefined or 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.

Side notes:

• I couldn’t fully understand the purpose or implementations of the UsedAsNumber flag. Any explanations would be welcomed.
• The pass did not handle operators like ValueSub, 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 ValueSub, 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.