

PREV PACKAGE NEXT PACKAGE  FRAMES NO FRAMES 
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 0address code for expr tree. 
gen1  output 1address code for expr tree. 
gen2  output 2address code for expr tree. 
gen3  output 3address code for expr tree. 
Main  demonstrate coexistence of jag based visitors. 
naive  output naive 0address 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 mixedmode expr tree. 
Exception Summary  

expr.yyException  thrown for irrecoverable syntax errors and stack overflow. 
Step 8: Code Generation Principles.
The register machine uses two addresses, but one has to refer to a small set of registers rather then to memory.
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.
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 0address 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.
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 0address 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 compiletime stack turns out to be sufficient to manage temporary memory for most hardware architectures as well as local labels for control structures.
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
1address 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(); };
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 1address 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.
A register machine is a special case of a 2address 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, fr1Either 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); }};Rootonly 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); };
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.
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 ...


PREV PACKAGE NEXT PACKAGE  FRAMES NO FRAMES 