Theory and Internals of JBurg and the BURM

Basic Components of a JBurg-generated BURM

JBurg generates bottom-up rewrite machines that use pattern-matching and dynamic programming to find a minimum-cost traversal of the tree in an initial label pass, and a second reduce pass that traverses the tree and emits code.

A Case Study: x + 1 and 1 + 2

Think for a moment about how a code generator generator can generate good code for the expressions x + 1 and 1 + 1. A code sequence for x + 1 (assuming x is an int) is:


ALOAD n
ICONST 1
IADD

But the code sequence for 1 + 1 can be constant-folded:


ICONST 2

How does one write code that can recognize these patterns? Hand-coded top-down traversal code might look like:


	switch ( currentNode.type )
	{
		...
		case PLUS:
		if ( isConstantInt ( currentNode.leftChild() ) && isConstantInt (currentNode.rightChild() ) )
		{
			int foldedValue = getConstantInt(currentNode.leftChild()) + getConstantInt(currentNode.rightChild());
			emitConstantInt ( foldedValue );
		}
		else if ( isConstantInt ( currentNode.rightChild() ) )
		{
		}
	}
	...

	// The instruction depends on the size of the constant.
	private void emitConstantInt ( int value )
	{
		if ( value < FIXME: check JVM spec )
				emit ( new ICONST(value) );
		else if ( value < ... )
				emit ( new BIPUSH(value) );
		else
			emit ( new LDC( constantPoolEntry(value) );
	}

And so on.

Dynamic Programming in a BURM

One of the difficult problems a code generator faces is that there are many choices that might be correct. For example, if the code generator sees PLUS(identifier, integer_literal), is this an integer addition or a floating-point addition? If the code generator works from the top down, then we might use one of these methods:

If the statement is of the form d = x + 1, (d being a double and x an int), then the assignment statement is the node that "knows" this is a floating-point addition. Information about this flows down the tree, from the assignment to a cast of the right-hand side of the assignment to double. The information doesn't have to flow very far, because programming languages are designed with this problem in mind: x + 1 can proceed as integer addition, to be converted to double just before it's assigned.
If, on the other hand, the statement is x + 1.0, then it's the floating-point constant that "knows" that the expression is floating-point: information flows up the tree.

Dynamic programming is a problem-solving technique that is very well suited to solving these kinds of problems. Dynamic Programming subdivides an overall problem (generating code from an AST) into a number of stages that can be solved individually. The nodes of a syntax tree form a natural hierarchy that can be readily adapted into stages (think of PLUS again: addition of two values is a self-contained problem that can be solved at the PLUS node's level). The possible solutions to a stage are called its states Each stage/state pair is also assigned a cost: if multiple possible solutions exist, then the least costly solution wins.

JBurg-type code emitters typically use a common set of states that correspond to the type of operand on a runtime stack, the value in a register, or the current statement. For example, in the JBurg pattern


    int PLUS(int, constant_int)

The states are int and constant_int.

The Principle of Optimality

Again, consider the rule PLUS(int, int) and the instruction sequence it will generate:

    code to push operand1 on the stack
    code to push operand2 on the stack
	IADD

One of the most important principles of computer architecture is that instructions such as IADD are not sensitive to the way their operands were derived: we can reason about the IADD, its inputs (two ints on the runtime stack), and its results (an int left on the runtime stack) without knowing how the inputs were computed. Similarly, the BURM pattern-matcher can report a successful match for the PLUS(int, int) pattern without knowing how its children get to the int state: it is enough to know that they have a bounded instruction sequence that can produce this state. This is known as the Principle of Optimality.

The "Principle of Non-Interference"

The JVM specification also does not place any constraints on the way that an IADD instruction's result may be used; the result is simply left on the runtime stack Downstream instructions do not influence the IADD at all. At the node level, this implies that as soon as we've computed the least-cost sequence that matches the PLUS node and all its children, we could go ahead and generate code. Thus a BURM could run in a single pass.

We might call this the "Principle of Non-Interference." JBurg does not consider the principle of non-interference to be valid over the entire tree. The principle of non-interference can be violated in two ways:

JBurg allows patterns to match multiple levels of the tree, for example, int = MULTIPLY(PLUS(int, int) constant_int).
This grammar can be normalized to remove this obstacle:
```
	int = MULTIPLY(generatedState1, constant_int): cost { Java }
	generatedState1 = PLUS(int, int): cost { Java }
	
```
The fun part of this transformation is figuring out how to factor the original rule's cost and Java information.
A node may need its children to emit specific code sequences, and so it can request that they attain specific goal states. Consider a PLUS node that chose to emit an IADD instruction, whose children were free to choose to emit 32-bit floating-point numbers: the IADD would produce garbage with these operands.

One of JBurg's pending tasks is to analyze a node's context to determine if the principle of non-interference holds for the node.

One-pass rewrites are especially suitable for tasks such as constant folding. The principle of non-interference holds through simple algebraic transformations: 1 + 1 is equivalent to 2. The one-pass rewrite becomes compelling when 1 + 1 must be translated into a bytecode instruction: the best instruction to use is an ICONST_2 instruction, but this is not obvious from inspection of the PLUS(constant_int, constant_int) INode -- the inspection happens in the labelling pass, and the addition happens in the reduction pass. If the entire subtree were collapsed into 2 at first inspection, then the labeller would have no trouble emitting an ICONST_2.

Transitive Closure

The transitive property simply says that if A = B, then B = C. Similarly, in a BURM, if a node can satisfy a particular state, then there may exist a set of states that are "equivalent" to the primary state. For example, an int state can obviously also satisfy a long state.

Transitive closures (also known as "simple transformation rules") are programmed into a JBurg specification using this synatax:


goal_state = original_state;

For example,

    long = int;

Complex Transformation Rules

Now consider the problem of transforming an int into an object. "int," in our hypothetical specification, is a goal state, not a node, so we cannot write a pattern-matching rule; and there isn't any way that the JVM can automatically convert an int into an object, so we can't write a transitive closure. We need some way to transform the int into an object.

One way to do this would be in inject CAST nodes into the tree in a semantic analysis pass; but JBurg's BURMs can also use "complex transformation" rules to do this directly.

An example of a complex transformation:


/*
 *  To get an object from an int we must construct an Integer.
 */
object_value = integer_value : 5
{
	//  Construct an Integer.
	InstructionList il = integer_value;

	//  cp is the BCEL constant pool generator for this class.
	int classIdx = cp.addClass ( "java/lang/Integer" );

	//  Prepend the new and dup instructions before the int value.
	InstructionHandle front = il.insert ( new NEW(classIdx) );
	il.append ( front, new DUP() );

	//  Now call  to initialize the Integer.
	il.append ( new INVOKESPECIAL ( cp.addMethodref ( "java.lang.Integer", "", "(I)V" ) ) );

	return il;
}

Non-Transitive Nature of Complex Transformations

The transitive property of algebra says that if A = B, and B = C, then A = C. (Note that it does not say that C = A, or even that C = B; that's the symmetric property). For example, int = byte and long = int works correctly according to the transitive property; machine architectures are set up to widen primitive arithmetic values without intervention at the instruction level.

Complex transformation rules do not satisfy the transitive property. Consider

Object = int { /* create Integer */ }
String = Object { /* call Object.toString() */ }; If we considered these states to be transitive, we would generate code that tried to construct a string by calling an int's toString() method. A JVM would reject this class with a verifier error (there's an int on the top of the stack, and we're trying to call a method? What's that all about?) and an analogous situtation in a C++ program would result in a segmentation fault, if the programmer were lucky.

Complex transformation rules inject additional information into the emitted code: the logic necessary to construct an Integer from an int, and to call the Integer's toString() method to obtain a String. The order in which these transformations occur is important.

Antecdedent States

There is a principle similar to the principle of optimality at work in a series of complex transformations: the transformation from Object to String does not need to know how the Object is constructed, it only needs to know that this stage must be in the Object state before it can transform the stage into the String state. More generally, any state in a stage may have a single antecedent state; the antecedent state may itself have an antecedent state, and so on, but the antecedent states cannot form a loop, or the reducer would not halt. TODO:Needs a formal proof and search of relevant literature for similar concepts.

Example of Complex Transformation Rules and Antecedent States

Again, let's work with the rules that convert an int to a String (assuming that other parts of the compiler have verified that this operation makes sense to the language being compiled):

int = INTEGER_LITERAL(void) { return new LDC(literal); }
Object = int { /* create Integer(int) */ }


String = Object { /* call Object.toString() */ };

The String state notes that its antecedent is Object, and the Object state notes that its antecedent is int; int has no antecedents. If the generated BURM's reducer decides to produce a string from this stage, it will first "reduce" the int state and emit an LDC instruction; it will then "reduce" the Object state and emit code that constructs an Integer from the int that the LDC instruction leaves on the stack; finally, the reducer reduces the String state and calls the Integer's toString() method.

Relationship Between States and ReturnType

Our constant-folding reductions have a "natural" type of Integer; 1+1 should result in 2. Most of the other reductions reduce to Java bytecode, but a procedure reduction could reduce to a BCEL Method object.

JBurg allows a state to specify a specific return type; for example, the constant_int state's return type is Integer:

ReturnType constant_int = Integer;

The default return type can be specified for the common case where a large majority of the states all use the same return type (e.g., InstructionList in the Falcon code emitter):

ReturnType InstructionList;

Dynamic Programming Tutorial

This tutorial is a more in-depth introduction to the theory of dynamic programming.

Compare the tasks necessary to generate code to the Common Characteristics of a dynamic programming problem, as noted in the tutorial:

The problem can be divided into stages with a decision required at each stage.
JBurg: Each level of the tree forms a stage.
Each stage has a number of states associated with it.
JBurg: The states are the possible code generation sequences that the emitter might emit.
The decision at one stage transforms one state into a state in the next stage.
JBurg: The stages and states model the information flow in the emitted code; when the emitted code runs, it will literally transform states as it performs its computations.
Given the current state, the optimal decision for each of the remaining states does not depend on the previous states or decisions.
JBurg: This is the Principle of Optimality
There exists a recursive relationship that identifies the optimal decision for stage j, given that stage j+1 has already been solved.
JBurg: The tree structure forms a natural recursive relationship. Remember that we are working from the bottom up, so stage j+1 solves the problem of emitting code for a node's children.
The final stage must be solvable by itself.
JBurg: The leaf nodes of the tree are recognized by NODE_TYPE(void) patterns.

The Internals of the generated BURM

TBD -- mention the label-reduce sequence, transitive closure in the labeller, antecedents, subgoals, minimum-cost goalseekers in the reducer, and the stack that builds up the reduced results.