Safia Abdalla is an open source developer and a maintainer on a project called nteract, but her pet topic is compilers. And, in her talk at Node.js Interactive, Abdalla explained the inner workings of the V8 compiler and how it can optimize the code it gets fed. Although Abdalla specifically focused on what goes on in the V8 compiler, she noted that there are many similarities to other compilers.
Crankshaft (vs. Full Codegen)
Most readers will be familiar with the concept of compiler -- that is, a program that converts source code into executable bytecode. However, there is a subset of compilers, called Optimizing Compilers that have a more specific role. Crankshaft is an optimizing compiler.
An optimizing compiler, explains Abdalla, is "one that more intelligently looks at the code it's translating to try and improve some aspects of the code." It does this by replacing poorly performant operations with performant ones. This often entails trying to reduce execution time by reducing the number of instructions the machine needs to run.
V8 also contains a non-optimizing compiler, called Full Codegen. All the code passes through Codegen and is compiled (and this is important as Abdalla shows later), but only code that is susceptible of being optimized gets passed onto Crankshaft.
The Full Codegen compiler is faster compiling than Crankshaft, because it does not have to search for ways of optimizing any code. However, the code it produces is generally slower. It also produces machine language code directly from what is called the abstract syntax tree (AST), while the Crankshaft compiler takes several intermediate steps between AST and machine language.
How does Crankshaft work?
The first step is to parse the code. "Parsing" in this context, says Abdalla, is the process of converting the source code into an AST. Both the Full Codegen and Crankshaft execute this parsing. The parsed code is never stored in memory. Every time the compiler needs the AST for a certain chunk of code, it needs to call the parser again to get it.
The keywords and phrases of your code are parsed into a parse tree, which is then converted into an AST -- a tree-data structure in which the roots and parent nodes are operators, and the children nodes are operands.
Once you have the AST, the compiler builds the Hydrogen representation, a higher level intermediary data structure. The hydrogen representation needs some information about the variable definition in the program, things like their type and scope, to be able to perform some optimizations.
As it's building the representation, Crankshaft already starts to incorporate some optimizations into the code. Although there are many possible strategies to optimize code, Abdalla focuses on function inlining -- the killing off dead code and common subexpression elimination. Function inlining consists of substituting the call to a function for the code the function would have executed. This is done because calling functions takes up a lot of operations at the stack level. As optimizing is all about reducing the number of operations executed, function inlining often makes a lot of sense. However, as Abdalla points out, this cannot be done in all cases. Using function inlining for recursive functions, for example, would be an especially bad idea.
The killing off dead of code happens after the Hydrogen representation has been constructed, and it is used to eliminate code that in the representation has no effect. These fragments of code can be introduced during the construction of the Hydrogen representation or could have been in the original code.
Related to the above, another optimization is the common subexpression elimination (or CSE). This process substitutes expressions within the Hydrogen representation with similar expressions which were encountered previously by the compiler. Basically, it is a way of de-duplicating code.
Once the Hydrogen representation has been optimized, it is translated into a Lithium representation. The code expressions in the Lithium representation are platform dependent, that is, the instructions are dependent on the processor of the underlying machine running the code.
The low level representation is finally translated into native code that the machine can run. Often, code in the Lithium representation can be directly translated to machine code.
But that's not all...
Abdalla points out that, after attempting all the optimizations, Crankshaft's job is not always done. Sometimes code will require de-optimizing. As Abdalla explains, Crankshaft "makes some optimistic assumptions about the types of data it will get in certain code blocks and it optimizes specifically for those types." However, sometimes those assumptions may be invalidated when the code is actually run, and Crankshaft may have to backpedal and use the unoptimized version of the code generated by the Full Codegen compiler.