There are several important components to the qbicc system that play a part in the generation of a native executable application.
The program graph is made up of classes which contain members. Any member which is executable contains a program graph. Each program graph comprises one or more basic blocks.
A basic block is defined as a terminating operation, or terminator, each of which may have one or more dependencies on other nodes
and which may have one or more successor basic blocks;
for example, an if node will have a successor for its true condition and one for its false condition,
whereas a throw node will have no successors.
Since each basic block has exactly one terminator, it can be said that the successors of the basic block are equal to the successors of its terminator.
Since each basic block can thus have several successors, including itself, the basic block graph may contain cycles.
Each executable program element (method, constructor, or class initializer) has an entry block which is the basic block that is entered when that element is executed.
Other than terminators, there are two other important categories of nodes: values and actions.
A value node is a node for any operation which produces some result that can be consumed by another node;
for example, the literal 123 and the expression foo + bar would be considered values.
An action node is a node which has a presence in the dependency graph of execution but neither yields a result nor terminates a block;
for example, a method invocation to a void method or a field or array member write would be considered an action.
A special value type called a phi value is used to represent a value whose interpretation depends on the predecessor basic block, having one different input value for each possible predecessor.
All three node types (terminators, values, and actions) may have a dependency on a predecessor node, as well as zero or more dependencies on consumed values for that node type. The graph formed by the terminator and its dependencies is a directed acyclic graph (DAG).
Some nodes are pinned to a specific basic block, such as phi nodes, and a terminator is always associated with a specific basic block. However, most other nodes are "floating", which is to say, not bound to any particular block.
Before the program graph can be lowered to an executable binary file, each node is scheduled to a specific basic block. In this way, the generation phase has access to a linear sequence of instructions which it may process in order.
The qbicc compilation process flows through two phases: add and generate. Each phase comprises multiple steps of processing. Broadly, the add phase is when classes are loaded and initialized, and the generate phase is when the loaded classes are traversed to emit the final image.
The overall flow runs like this:
The steps can be broken down as follows:
-
Add phase:
-
Pre-add hooks: these hooks run before any class loading is done, and are implemented as a
Consumer<CompilationContext> -
Add: each entry point is recursively processed, method bytecodes are translated into program graphs, and classes are initialized; also, single-pass optimizations may be performed, and integrity checks are done on the resultant graph
-
Post-add hooks: these hooks run after all reachable members have been processed but before copy takes place
-
-
Generate phase:
-
Copy: all reachable members are copied into the final lowered and optimized graph; also, the second pass of two-pass optimizations may be performed, and integrity checks are done on the resultant graph
-
Pre-generate hooks: these hooks run after copying is complete, generally to set up generation
-
Generation: each executable member is passed to a series of visitors implementing
ElementVisitor, which are expected to produce the back end lowered program code for linkage -
Post-generate hooks: these hooks run after generation to perform completion steps, such as generating supplemental object files and executing the toolchain linker
-
If all steps complete without error, the compilation is successful; otherwise, compilation halts after the first step that produces an error.
The CompilationContext interface provides a means for hooks and add steps to recursively enqueue additional reachable members for processing.
In this way, every step of the process has the capability to add (during the add phase) or skip (during the add or generate phases) a member during processing.
The add phase is implemented by the BasicBlockBuilder interface.
As bytecodes are parsed from each executable member, the builder is called for each operation to assemble the basic block graph of the program.
Multiple chained implementations of this interface are used to perform various optimizations, transformations, and checks;
for example, a BasicBlockBuilder implementation may implement the if operation by examining the condition, determining whether it is constant, and if so, replacing the operation with a simple goto.
Another implementation may examine the arguments of binary operations such as add to ensure that the argument types are compatible, and report an error if that is not the case.
Implementations may delegate operations to the next step in the chain as needed.
Once the phase is complete, each reachable executable member will have an associated directed graph of basic blocks.
The program is lowered by copying the program graph of each reachable member, using the special Copier class.
The copy process works by pairing a NodeVisitor with a BasicBlockBuilder.
Each program graph is traversed by the visitor, resulting in a replacement entry block for each program element.
The resultant rewritten program graphs are then traversed in a backend-specific manner to produce object files and to ultimately link the final executable.
The set of BasicBlockBuilder implementations which are used in the generate phase will differ to an extent from what was used during the add phase.
For example, virtual method invocations may be lowered to function calls during this stage, using information gathered during the add phase.