Package step8

Step 8: Code Generation Principles.

See:
          Description

Interface Summary
expr.yyActions interface between grammar and actions.
expr.yyInput must be implemented by a scanner object to supply input to the parser.
 

Class Summary
expr representing an arithmetic expression as a tree.
expr.Commutative base class to mark an operator property.
expr.yyLex  
expr.yyTree tree factory.
expr.yyTree.Add  
expr.yyTree.Div  
expr.yyTree.Minus  
expr.yyTree.Mod  
expr.yyTree.Mul  
expr.yyTree.Sub  
gen0 output 0-address code for expr tree.
gen1 output 1-address code for expr tree.
gen2 output 2-address code for expr tree.
gen3 output 3-address code for expr tree.
Main demonstrate coexistence of jag-based visitors.
naive output naive 0-address code for expr tree.
R manages registers and output for a register machine.
R.Float describes a result in a floating point register.
R.Long describes a result in a general register.
reg output register machine code for mixed-mode expr tree.
 

Exception Summary
expr.yyException thrown for irrecoverable syntax errors and stack overflow.
 

Package step8 Description

Step 8: Code Generation Principles.

Architectures

Real machines have complex architectures that are usually difficult to use to their full potential. However, real machines are likely to combine traits of some typical architectures which will be considered here. The characteristic aspect is how many memory addresses are part of a binary arithmetic instruction.

0-Address Machine

1-Address Machine

2-Address Machine

3-Address Machine

Register Machine

The register machine uses two addresses, but one has to refer to a small set of registers rather then to memory.

Tree Markup

As an example consider - (1 % ( 2 + 3 * 4 - 5 / 6 )) which corresponds to the following tree:

One approach to code generation would be to represent the expression in postfix notation and simulate a stack on each hardware architecture, but there are more appropriate solutions for various typical machine architectures.

A goal is to minimize the memory requirements during evaluation. This is accomplished by varying the order in which the subtrees are visited based on the operator in the root node -- one of the central design features of jag.

expr.pj is a frontend which recognizes arithmetic expressions with floating point and integer literals and relies on Node to display an indented tree and on expr.Commutative to mark operators as commutative:

expr : add | sub | mul | div | mod | minus
  | '+' expr
  | '(' expr ')'
  | Double | Long;

<Commutative> add : expr '+' expr <Add>;
<Node>        sub : expr '-' expr <Sub>;
<Commutative> mul : expr '*' expr <Mul>;
<Node>        div : expr '/' expr <Div>;
<Node>        mod : expr '%' expr <Mod>;
<Node>        minus: '-' expr     <Minus>;
%%
  protected static class Commutative extends Node { }

$ mkdir step8
$ java -jar pj.jar -jay -scanner:static - -tree:static - expr.pj > step8/expr.java
$ javac step6/Node.java step8/expr.java
$ java step8.expr
- (1 % ( 2 + 3 * 4 - 5 / 6 ))
Minus
  Mod 1
    Sub
      Add 2
        Mul 3 4
      Div 5 6

Interfaces would be a more general way to mark operator properties, but pj does not (yet?) support markup interfaces for tree factory generation.

0-Address Machine

A 0-address or stack machine works on arguments on a -- more or less infinite -- stack. Arithmetic instructions such as add have no explicit arguments:

There have to be additional instructions such as load and store to transfer information between some storage and the stack. These instructions need addresses.

naive.jag implements a naive postorder visit to an expression tree which produces 0-address code but can waste memory:

$ java -jar jag.jar < step8/naive.jag > step8/naive.java
$ javac step8/naive.java
$ java step8.naive
- (1 % ( 2 + 3 * 4 - 5 / 6 ))
load    1
load    2
load    3
load    4
mul
add
load    5
load    6
div
sub
mod
minus

gen0.jag generates more efficient stack machine code for the tree introduced in Tree Markup:

$ java -jar jag.jar < step8/gen0.jag > step8/gen0.java
$ javac step8/gen0.java
$ java step8.gen0
- (1 % ( 2 + 3 * 4 - 5 / 6 ))
load    1
load    4
load    3
mul
load    2
add
load    5
load    6
div
sub
mod
minus

gen0.jag exploits the commutativity of addition and multiplication. This code requires less stack space because it defers loading the left leaf operands of commutative operators until the operators are actually evaluated.

To accomplish that, gen0.jag contains exactly one more pattern then naive.jag:

List: Object Object { $1; $2; $0; } // default: postorder
  | Object          { $1; $0; };

Commutative: Number Object { $2; $1; $0; }; // optimization

Add:    { `"add\n"`; }; // machine instructions
  // ...
Number: { `"load\t"+$0.intValue()+"\n"`; };
The additional pattern recognizes just the case that can be optimized; the corresponding action reverses the order of subtree traversal and therefore loads the Number onto the stack just before it is needed.

The action employs an additional shorthand: {$0} or $0; is expanded as a recursive traversal of the root node where the pattern lookup is modified to consider only patterns with no descendants. This shorthand permits an elegant specification of the machine instruction names attached as very simple actions to their corresponding classnames as patterns.

1-Address Machine

A 1-address machine works much like a pocket calculator with a display. Arithmetic instructions such as add have a single argument and combine it with the display:

There have to be additional instructions such as load and store to transfer information between some storage and the display.

gen1.jag exploits the commutativity of addition and multiplication to generate efficient code for the tree introduced in Tree Markup. Constants must be loaded directly:

$ java -jar jag.jar < step8/gen1.jag > step8/gen1.java
$ javac step8/gen1.java
$ java step8.gen1
- (1 % ( 2 + 3 * 4 - 5 / 6 ))
load    5
div     6
store   temp1
load    4
mul     3
add     2
sub     temp1
store   temp1
load    1
mod     temp1
store   temp1
load    0
sub     temp1

The code can be substantially improved if there is a 0-address instruction minus to change the sign of the display.

Most hardware architectures need to store temporary results. A Temp object manipulates an integer value (initialized to zero) as follows:

get() increments the current value and returns the new value.
ref() returns the current value.
free() returns the current value and decrements it.

This compile-time stack turns out to be sufficient to manage temporary memory for most hardware architectures as well as local labels for control structures.

2-Address Machine

2-address machines are the theoretical version of a very common architecture. An arithmetic instruction has two arguments, combines them, and overwrites one of them with the result:

There should be an additional instruction such as move to transfer information between storage cells.

gen2.jag exploits commutativity and generates reasonable code for the tree introduced in Tree Markup. Constants must be loaded directly:

$ java -jar jag.jar < step8/gen2.jag > step8/gen2.java
$ javac step8/gen2.java
$ java step8.gen2
- (1 % ( 2 + 3 * 4 - 5 / 6 ))
move    temp1,0
move    temp2,1
move    temp3,3
mul     temp3,4
add     temp3,2
move    temp4,5
div     temp4,6
sub     temp3,temp4
mod     temp2,temp3
sub     temp1,temp2

This code is very poor. It can be improved if there is a 1-address instruction minus to change the sign of a storage cell. However, Temp can only be used for memory management by creating each result in the location which Temp would create next. The solution for the register machine below shows how much better code can be obtained with a more sophisticated memory management.

The elegance of the pattern search through superclasses implemented by jag lies in the fact that a few general rules will already do most of the work. Specialized rules can be added, even later, to improve code generation in certain situations. The patterns for expr.Commutative demonstrate, however, that the sequential search through the list of patterns for one root node class has to be considered when an action is added for a special case: the Number Number case has to be explicitly excluded before the Number Object case can be dealt with:

Commutative: Number Number // revert to superclass of node
  | Number Object          { {$2}; // optimization: commutative
                             {$0}; `"temp"+ temp.get() +","`; {$1}; `"\n"`;
                                            temp.free();
                           };

3-Address Machine

3-address machines are an important theoretical case because their code (triples or quadruples) can be optimized and mapped to other architectures easily.

An arithmetic instruction has three arguments, combines two, and overwrites the third with the result:

There should be an additional instruction such as move to transfer information between storage cells.

gen3.jag is simpler and generates more compact code then gen2.jag for the tree introduced in Tree Markup:

$ java -jar jag.jar < step8/gen3.jag > step8/gen3.java
$ javac step8/gen3.java
$ java step8.gen3
- (1 % ( 2 + 3 * 4 - 5 / 6 ))
mul     temp1,3,4
add     temp1,2,temp1
div     temp2,5,6
sub     temp1,temp1,temp2
mod     temp1,1,temp1
sub     temp1,0,temp1

The code can be improved if there is a 1-address instruction minus to change the sign of storage cell.

Temp can be used for memory management by creating each result in the location which Temp would create next.

Register Machine

A register machine is a special case of a 2-address machine. It has relatively few, fast registers with simple addresses which serve as source and target for arithmetic instructions:

Modern RISC architectures arrange for very many registers; however, register management is still not trivial because registers are also needed to address memory.

reg.jag generates more efficient code then gen2.jag for the tree introduced in Tree Markup:

$ java -jar jag.jar < step8/reg.jag > step8/reg.java
$ javac step8/reg.java
$ java step8.reg
- (1 % ( 2 + 3 * 4 - 5 / 6 ))
        load    r0, 3
        mul     r0, 4
        add     r0, 2
        load    r1, 5
        div     r1, 6
        subr    r0, r1
        load    r1, 1
        modr    r1, r0
        load    r0, 0
        subr    r0, r1

expr.pj can generate Long and Double leaves. A typical register machine has different registers for integer and floating point arithmetic, and in the spirit of C arithmetic must use floating point registers if at least one operand is a Double value. A small change in the input causes some conversion operations (loading a floating point register from an integer register) to be introduced and there is some floating point arithmetic:

$ java step8.reg
- (1 % ( 2. + 3 * 4 - 5 / 6 ))
        load    r0, 3
        mul     r0, 4
        loadfr  fr0, r0
        addf    fr0, 2.0
        load    r0, 5
        div     r0, 6
        loadfr  fr1, r0
        subfr   fr0, fr1
        loadf   fr1, 1.0
        modfr   fr1, fr0
        loadf   fr0, 0.0
        subfr   fr0, fr1
Either way the generated code is much shorter then previous versions because the registers are not managed as a stack.

Two auxiliary classes, R.Long and R.Float, both derived from an abstract class R, manage the registers and their objects represent the result type of a generated machine instruction.

The pattern list for a binary operation has to sort out the leaves before it can deal with the general case:

List: Long Long { // two integer literals
    $$ = new R.Long((String){$0}, new R.Long($1), $2);
  } | Number Number { // two literals, at least one floating point
    $$ = new R.Float((String){$0}, new R.Float($1), $2);
  } | Long List {{ // an integer literal and an expression
    R right = (R)$2;
    $$ = right instanceof R.Long ?
      (R)new R.Long((String){$0}, new R.Long($1), right) :
      (R)new R.Float((String){$0}, new R.Float($1), right);
  }} | Number List {{ // a floating point literal and an expression
    R right = (R)$2;
    $$ = new R.Float((String){$0}, new R.Float($1), right);
  }} | List Long {{
    R left = (R)$1;
    $$ = left instanceof R.Long ?
      (R)new R.Long((String){$0}, left, $2) :
      (R)new R.Float((String){$0}, left, $2);
  }} | List Number {{
    R left = (R)$1;
    $$ = new R.Float((String){$0}, left, $2);
  }} | List List {{ // general case
    R left = (R){$1}, right = (R)$2;
    if (left instanceof R.Long && right instanceof R.Long)
      $$ = new R.Long((String){$0}, left, right);
    else
      $$ = new R.Float((String){$0}, left, right);
  }};
A few more special cases for commutative operators can further improve the generated code:
Commutative: Long Long // revert to superclass of node
  | Number Number // revert to superclass of node
  | Long List {{
    R right = (R)$2;
    $$ = right instanceof R.Long ?
      (R)new R.Long((String){$0}, right, $1) :
      (R)new R.Float((String){$0}, right, $1);
  }} | Number List {{
    R right = (R)$2;
    $$ = new R.Float((String){$0}, right, $1);
  }};
A minus sign is mapped to sub:
Minus: Long {
    $$ = new R.Long("sub", new R.Long(new Long(0)), $1);
  } | Number {
    $$ = new R.Float("sub", new R.Float(new Float(0)), $1);
  } | List {{
    R right = (R)$1;
    if (right instanceof R.Long)
      $$ = new R.Long("sub", new R.Long(new Long(0)), right);
    else
      $$ = new R.Float("sub", new R.Float(new Long(0)), right);
  }};
Root-only rules contain the machine instructions as usual and two more rules deal with trivial expressions:
Add: { $$ = "add"; }; // generic machine instructions
Mul: { $$ = "mul"; };
Sub: { $$ = "sub"; };
Div: { $$ = "div"; };
Mod: { $$ = "mod"; };

Long: { $$ = new R.Long($0); }; // trivial cases
Double: { $$ = new R.Float($0); };

Register Allocation

reg.jag also contains a register allocator.

R is a hidden abstract class representing a register as an array index. The array element is used to track the reservation. This model would have to be refined once registers have to be paged to memory.

R.get(boolean[]) implements the register allocation algorithm shared by the subclasses.

R.rX ist used in each object to indicate which register the object represents.

Concrete subclasses R.Long and R.Float represent registers for Long and Double arithmetic. The constructors create machine instructions and track the result registers. The necessary constructors can be inferred from the rules in reg.jag.

R.Float has an additional constructor to convert from Long in a general register into Double in a floating point register.

If a register needed to be paged to memory, R.get(boolean[]) could call an abstract (subclass) method to accomplish that. The register description would then have to reflect how the value can be restored. Code to restore the value to a register would be generated when a constructor consumes a register value that has been paged.

Multiple Visitors

Each execution of jag creates source code for a Java class. Therefore, jag-based visitors can easily coexist in the same program, as Main.java demonstrates. This program reads an expression from standard input and for each class name specified as a command argument creates a visitor and applies it to the expression tree.

$ javac step8/Main.java
$ java step8.Main step8.naive ...
- (1 % ( 2 + 3 * 4 - 5 / 6 ))
step8.naive:
load    1
...