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, which in turn contain a sequence of nodes which define the program behavior.
A basic block is defined as a directed acyclic graph of nodes, with a single entry point at the start of the block and a single exit point at the end of the block.
Additionally, the nodes within a basic block are organized into a sequence by the scheduler.
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.
In qbicc, blocks accept parameters which are named by a special kind of identifier called a slot. Parameters are represented by a special value type. Arguments are passed in to basic blocks by terminators which pass control from one block to another, or by entry into a function or method.
Every program operation is represented as an atom called a node. A node represents a discrete value or computation that must be performed by the program.
Nodes may have a dependency on zero or more value nodes which are consumed by the operation.
A node may also be ordered by implementing the OrderedNode interface. Such nodes always have exactly one additional dependency on a predecessor node. Ordered nodes usually (but do not always) form a linear linked list.
All dependencies of a node are guaranteed by the scheduler to have been scheduled before the node itself. Since this may be impossible for certain values which are used and defined in blocks which form a loop, values that flow along loop back-edges are usually passed in using block parameters.
A value node is a node for any operation which produces some result that can be consumed by another node;
for example, the expression foo + bar would be considered a value. A value always has a type that indicates how the value is to be interpreted.
A literal is a value which represents an immutable piece of data. This can either be a simple value like the integer 123 or global variable foo, a composite value like an array of [ 12, 34 ], or certain kinds of expressions comprising literals like foo[123].
Block parameters are represented using a dedicated value node. The node identifies the parameter by slot and represents the merging of possible argument values for that slot from all incoming blocks. This replaces the concept of phi nodes found in other SSA-based systems.
An action 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 store to memory or a safepoint poll would be considered an action.
Every block ends with a terminating operation, or terminator, which may have one or more successor basic blocks;
for example, an if node will have one 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
overall control flow graph formed by basic blocks may contain cycles.
Some nodes are pinned to a specific basic block, such as block parameter 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.
After a subprogram graph is built, each reachable node in the final graph is scheduled to a specific basic block. In this way, any compilation stage has access to a linear sequence of instructions which it may process in order.
The qbicc compilation process flows through multiple phases. Each phase comprises multiple steps of processing.
The overall flow runs like this:
The steps can be broken down as follows:
-
ADD phase:
-
Possible program execution is traced from initial entry points
-
Classes are loaded and initialized as needed
-
Optimizations are applied based on configuration and locally-observable information
-
Reachable program elements recursively cause other elements to become reachable
-
Run time checks are inserted for array range checking, null reference checking, etc.
-
Static checks are performed to enforce graph invariants
-
This is the only phase in which new program elements may become reachable
-
-
ANALYZE phase:
-
Possible program execution is traced from the same initial entry points
-
Each program element graph is copied into a new graph, applying new optimizations based on locally-observable information as well as information gathered in the prior phase execution
-
This phase is the primary phase for major optimizations to take place
-
Static checks are performed to enforce graph invariants
-
The overall program graph is reduced as unreachable nodes and elements are pruned during copy
-
-
LOWER phase:
-
Possible program execution is traced from the same initial entry points
-
Each program element graph is copied into a new, lowered graph which gives up some degree of optimizability in favor of more closely modeling the target system
-
Some last-minute peephole optimizations are still performed
-
-
GENERATE phase:
-
Each reachable executable member is passed to handlers which are expected to produce the back end lowered program code for linkage
-
Any generated target-language sources are compiled
-
All object files are linked into the final image
-
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 subsequent phases) a member during processing.