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.

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

`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.
- 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)
```

`int`

and constant_int.
`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
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: The fun part of this transformation is figuring out how to factor the original rule's`int = MULTIPLY(generatedState1, constant_int):`

*cost*{*Java*} generatedState1 = PLUS(int, int):*cost*{*Java*}*cost*and

information.*Java* - 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`

.

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:

`For example,`

goal_state=original_state;`long = int;`

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;
}

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() */ }`

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

`int = INTEGER_LITERAL(void) { return new LDC(`

literal); }`Object = int { /* create Integer(int) */ }`

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

;

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:

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):

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.

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