Lburg2

Eric Chan <ericchan@cs.stanford.edu>

Initial date:
  7-17-2001

Last updated:
  $Author: ericchan $
  $Date: 2002/06/17 18:04:50 $

----------------------------------------------------------------------

Overview

These notes describe some important changes I made to lburg.  To avoid
confusion, I will refer to the original version as lburg1 and to the
new version as lburg2.  I have edited both the win32 and linux
Makefiles so that lburg2 processes .bg2 files, while lburg1 processes
.bg files.

Input files for lburg1 must be modified to work with lburg2; otherwise
they will not parse correctly.  This is because lburg2 supports
"actions" for rules instead of strings, whereas lburg1 does not.  As a
result, the syntax for specifying rules is different.

The key changes in lburg2 are:

- Support for n-ary trees.
- Symbolic names for terminals.
- User-defined actions.
- User-defined state management.
- More cost expression options.

At the bottom of this document I also point out some implementation
details.

----------------------------------------------------------------------

Macros

lburg1 requires that the .bg file define macros LEFT_CHILD and
RIGHT_CHILD to refer to a node's children.  Since lburg2 supports
n-ary trees, these macros have been replaced with

    NTH_CHILD(p, n)

which must return a pointer to the child index [n] of node [p].  The
indices are 0-based, so that n = 0 refers to the first child, n = 1
refers to the second child, etc.

For example:

    typedef struct node_s
    
        int op;
	int value;
	int num_kids;
	struct node_s *kids[10];
	void *state;
    } node_t, *node_p;

    #define NODEPTR_TYPE     node_p
    #define STATE_LABEL(p)   ((p)->state)
    #define OP_LABEL(p)      ((p)->op)
    #define NTH_CHILD(p, n)  ((p)->kids[n])

----------------------------------------------------------------------

Declaring Terminals

In lburg1, a terminal is assigned a constant integer value.  For
example:

    %term ADD = 7

In lburg2, a terminal may be assigned any constant, integer-valued
expression.  Here are valid terminal declarations:

    %term ADD     = OP_ADD
    %term ADD_F4  = ((OP_ADD << 16) | OT_FLOAT4)

However, the declaration

    %term ADD     = my_function(OP_ADD)

is not valid because the expression does not evaluate to a
compile-time integer constant.

                             ***

lburg1 checks to make sure that terminal constants are unique.  For
example, lburg1 will raise an error on the following input:

    %term ADD = 7
    %term SUB = 7

because two terminals have the same constant value.  However, lburg2
does not check for uniqueness.  This is because lburg2 allows
arbitrary expressions (as discussed above), which cannot be evaluated
immediately.  Fortunately, the error will still be detected when
attemping to compile the generated code.

                             ***

In lburg1, one can declare multiple terminals on one line.  For
example:

    %term ADD=306 ADDF=305 ADDI=309

lburg2 does not support this; each terminal must be declared on a
separate line.

A common mistake is to place a semicolon after the terminal
declaration, e.g.

    %term ADD = 7;

This is syntactically correct, but probably not what you want.  The
effect is similar to using a semicolon at the end of a #define in C:

    #define ADD 7;  /* probably not what you want */

----------------------------------------------------------------------

Using Symbolic Expressions With Terminals

This section describes a handy technique made possible by symbolic
expressions in terminal declarations.

lburg1 uses the user-defined OP_LABEL macro to identify nodes.  For
example, passgen_lb.bg defines OP_LABEL this way:

    #define OP_LABEL(p) ((p)->lb.op)

It is useful sometimes to use the operand type for instruction
selection in addition to the opcode.  For example, the exact
instructions emitted from an ADD operation often depend on the operand
types.  One way of handling this situation is as follows:

    node: ADD(node, node) "1"
        EMIT
        {
            switch ($1->optype)
            {
                case OT_FLOAT3:
                    /* handle float3 case */
                    break;

                case OT_MATRIX3:
                    /* handle matrix3 case */
                    break;

                /* all other cases go here */
            }
        }
        ;

Instead of defining one ADD terminal and then switching on a number of
operand types, a better approach is to define specific ADD terminals
for each type:

    %{
        /* other initialization code */

        #define PACK(x, y)   (((x) << 16) | (y))
        #define OP_LABEL(p)  (PACK((p)->op, (p)->optype))

    %}

    // An example with 2 ADD terminals,
    // one for 3-vector floats, one for
    // a 3x3 matrix of floats.

    %term ADD_F3 = PACK(OP_ADD, OT_FLOAT3)
    %term ADD_M3 = PACK(OP_ADD, OT_MATRIX3)

    %%

    node: ADD_F3(node, node) "1"
        EMIT
        {
            /* handle float3 case */
        }
        ;

    node: ADD_M3(node, node) "1"
        EMIT
        {
            /* handle matrix3 case */
        }
        ;

Although this approach involves writing more rules, it is more
flexible.  It may be the case, for example, that you wish to use a
multiply-add (MAD) instruction, but the instruction only works on
3-vectors or 4-vectors.  Then we can write rules such as:

    node: ADD_F3(MUL_F3(node, node), node) "1"
        EMIT
        {
            /* emit MAD instruction here */
        }
        ;

    node: ADD_F4(MUL_F4(node, node), node) "1"
        EMIT
        {
            /* emit MAD instruction here */
        }
        ;

These rules will be used only if the operand types are 3-vectors or
4-vectors of floats.

----------------------------------------------------------------------

Declaring Rules

Rules in lburg2 are now defined by the following grammar:

  rule       -> nonterm : tree cost codeblocks ;

  nonterm    -> ID

  tree       -> ID
             -> ID ( tree_list )

  tree_list  -> tree
             -> tree , tree_list

  codeblocks -> codeblocks codeblock
             -> LAMBDA

  codeblock  -> ID CBLOCK

  cost       -> STRING_EXPR
             -> LAMBDA

In the above grammar, CBLOCK is a string that begins with a left curly
brace '{' and ends with a matching right curly brace '}'.  STRING_EXPR
is a string that is enclosed by double-quotes and does not contain a
newline.

This grammar is quite different from that of lburg1.  In particular,
note these changes:

- lburg2 supports n-ary trees, not just binary trees.  Each node can
  have at most MAX_KIDS children.  MAX_KIDS is defined in lburg.h.

- The template string has been replaced with user-defined actions (see
  nonterminal 'usercode').  These will be discussed below in detail.

- The 'cost' expression must be enclosed within double-quotes.

- Each rule definition must end with a semicolon.

Here is an example of a rule specified in lburg1:

  value: ADD(value, value) "example_string"  1 + Cap(ALPHA)

Here is how this rule is specified in lburg2:

  value: ADD(value, value) "1 + Cap(ALPHA)" ;

Notice in the latter declaration that the template string is gone, the
cost expression is enclosed in double-quotes, and that there is a
semicolon at the end.

Why the changes to the rule declaration syntax?  I made these changes
to facilitate text parsing.  In particular, I wanted developers to
have the ability to use whitespace freely when defining rule actions.
Modifying the syntax in the manner described above simplifies the
parser.

----------------------------------------------------------------------

Rule Actions

Rule actions are new to lburg2.  An action is a block of C code
associated with a particular rule.  Here is a simple example:

    node: ADD(node, node) "1"
        POST
        {
            $1->value = $2->value + $3->value;
        }
    ;

This specifies a rule with a cost of 1 and a single action labeled
POST.  Each rule can support 0 or more actions.  Here is an example
with 2 actions, labeled PRE and POST:

    node: ADD(node, node) "1"
        PRE
        {
            printf("We found an ADD node.\n");
        }

        POST
        {
            $1->value = $2->value + $3->value;
        }
    ;

Each action for a given rule must be given a unique label.  lburg2
will raise an error if a conflict is found.  However, the same label
may be used by actions in different rules.  For instance, you can
declare a POST action for every rule, as long as each rule only has
one action labeled POST:

    node: ADD(node, node) "1"
        POST
        {
            $1->value = $2->value + $3->value;
        }
    ;

    node: SUB(node, node) "1"
        POST
        {
            $1->value = $2->value - $3->value;
        }
    ;

One restriction is that labels may not clash in the generated code's
global namespace.  This is because each lburg2 generates code with
each label defined as a global enumerated constant.  Thus, you must be
careful to avoid choosing a label the same as, say, the name of a
global variable.  Finally, any action with a label of COST may be
executed automatically upon calling lburg2's emitted _label function.
This is explained in more detail below.

                             ***

lburg2 provides a yacc/bison-like mechanism for referring to nodes in
the rule pattern.  $1 always points to the root node.  All other nodes
are numbered in increasing order by a pre-order depth-first traversal.
For example, given the following tree pattern

    ADD(a, b)

    $1 points to the ADD node,
    $2 points to the 'a' node,
    $3 points to the 'b' node.

Here is a more complex example:

    ADD(MUL(a, b), SUB(c, DIV(d, e)))

    $1 points to the ADD node,
    $2 points to the MUL node,
    $3 points to the 'a' node,
    $4 points to the 'b' node,
    $5 points to the SUB node,
    $6 points to the 'c' node,
    $7 points to the DIV node,
    $8 points to the 'd' node,
    $9 points to the 'e' node.

In other words, nodes are numbered in increasing order (starting from
1) as you read the expression from left to right.  This is an easy way
to remember the numbering scheme.

lburg2 ignores the $n construct if $n appears within a C comment, a
C++ comment, or a string.  Otherwise, lburg2 treats $n as a node
pointer. lburg2 will check that the value of 'n' is within a valid
range.  For example,

    node: ADD(node, node) "1"
        POST
        {
            $1->value = $2->value + $4->value;
        }
    ;

will cause lburg2 to raise an error because the rule pattern
has only three nodes, but the action contains $4, a
reference to a non-existent fourth node.

The data type of $n is NODEPTR_TYPE.

                             ***

Rule actions are typically invoked during reduction.  To
invoke a rule, you need:

- the rule number
- the action's label
- a pointer to the root expression node
- user-defined data (optional)

lburg2 emits a function named _action for convenience:

    static void _action(
        int                rule_number,
        RULEACTION_LABEL   rule_label,
        NODEPTR_TYPE       root_node,
	void *             ACTION_DATA);

The parameter [ACTION_DATA] is used for passing application-specific
data to the rule actions.  It is not used in any way by lburg2.  If
you have no data to pass, set [ACTION_DATA] to NULL.  To access this
data from within an action, use the ACTION_DATA macro.  The data type
of ACTION_DATA is a (void *).  For example:

    node: ADD(node, node) "1"
        POST
	{
            int *count = (int *) ACTION_DATA;
	    *count++;

	    /* do other stuff here */
	}
     ;

Here is an example of a reduce function that calls the POST action:

    static void
    reduce (NODEPTR_TYPE p, int nt)
    {
        int i;
        int rulenum = _rule(STATE_LABEL(p), nt);
        short *nts = _nts[rulenum];
        NODEPTR_TYPE kids[MAX_KIDS];

        for (i = 0; nts[i]; i++)
        {
            reduce(kids[i], nts[i]);
        }

        /* call action here */
        _action(rulenum, POST, p, NULL);
    }

If you specify an invalid label for an action (e.g., maybe you omitted
the POST action for some rules), the _action function does nothing.
No warning is raised.

----------------------------------------------------------------------

Cost Expressions

Cost expressions are declared similarly in lburg2 as in lburg1, except
that the expression must be contained within double-quotes.  lburg2
also supports the $n construct within these expressions, so the cost
can be a function of the rule's pattern nodes.  Here is an example for
the nv20 vertex code generator:

  #define MAX_COST 0x7fff

    
  // divide -- general case
  float1: DIV_F1(float1, float1) "2"
    EMIT
    {
        _instr(RCP, "%.x, %.x", $1->index, $3->index);
        _instr(MUL, "%.x, %.x, %.x", $1->index, $2->index,
               $1->index);
    }
    ;

  // divide -- special case, 1.0f / x
  float1: DIV_F1(float1, float1)
    "is_constant_scalar($2, 1.0f) ? 1 : MAX_COST"
    EMIT
    {
        _instr(RCP, "%.x, %.x", $1->index, $3->index);
    }
    ;

Notice that the first rule has a fixed cost of 2.  The second rule, on
the other hand, will have a cost of 1 only when the numerator is 1.0;
otherwise, the cost for this rule will be very high.  Thus, given a
DIV_F1 node, lburg2 will choose the second rule (which requires only 1
instruction) in the special case that the numerator is 1.0, but will
choose the first rule (which requires 2 instructions) in all other
cases.

Using cost expressions this way can be very useful, but beware of
uninitialized values.  Cost expressions are evaluated in the _label
function, not the reducer.  This means that a cost expression cannot
refer to a node field that is only set during a reduction.

----------------------------------------------------------------------

User State and the COST Action

Any rule action labeled COST may be executed in lburg2's _label
function.  For a given rule R with tree pattern P, the COST action for
R is executed after the cost expressions for all of P's children have
been evaluated, but before the cost expression for R is evaluated.
This facility was added to lburg2 to allow users to pass information
between nodes during the labeling process; this information is
typically used for more complex cost expressions.

                             ***

lburg2 also provides a mechanism for keeping track of additional
per-node state.  User state is declared in the terminals section
(i.e., before the first %%) using the following syntax:

   %state <type> identifier-list

For example:

   %state <int>    constant
   %state <char *> name token usercode

These declarations tell lburg2 to keep track of an integer named
[constant] and three character strings, named [name], [token], and
[usercode].

lburg2 places these variables inside a union.  The example above would
be equivalent to creating this union:

   union
   {
       int constant;
       char *name, token, usercode;
   };

If you wish to use multiple pieces of state information at once, you
can use structs.  For example:

   %{
       /* other setup code */

       struct my_state_s
       {
           float x, y, z;   
       };
   %}

   /* other terminal declarations */

   %state <int>                constant
   %state <char *>             name token usercode
   %state <struct my_state_s>  position

Note that the state declaration must be on a single line.  Whitespace
is allowed but a newline is not.

                             ***   

We have discussed how to specify user state information, but not how
to use it.  lburg2's _label function allocates this union for each
node in the given tree.  In particular, user state is always allocated
(but uninitialized) before any rule's COST action is invoked on that
node.

lburg2 exports a macro, _UST, which returns a pointer to the union
described above.

   #define _UST(p)  /* returns pointer to
                       user state for node p */

Using the state declarations above, we can do the following:

   _UST(p)->constant = 7;

   _UST(p)->name = "ref_node";

   _UST(p)->position.x = -3.0f;
   _UST(p)->position.y = 17.0f;
   _UST(p)->position.z = 0.0f;

Remember that the user state is maintained as a union, not a struct.
It is up to the user to interpret this information consistently.

lburg2 also exports a macro, _COPY_UST, which copies user state
directly from one node to another.

   #define _COPY_UST(dst, src)

After using _COPY_UST, node [dst] will have the exact same user state
as node [src].  Be careful of pointer aliasing.

                             ***

lburg2's COST actions can be combined effectively with user state to
perform more sophisticated instruction selection.  Here is an example
that illustrates one possible technique.  The goal is to recognize a
lerp, i.e.  an expression of the form:

   a * x + b * (1 - x)

Since a valid lerp may be written in a number of ways, we want to use
a rule hierarchy such as the following:

   float1: ADD(lerp1, lerp2);
   float1: ADD(lerp2, lerp1);

   lerp1: MUL(float1, float1);

   lerp2: MUL(float1, SUB(const_one, float1));
   lerp2: MUL(SUB(const_one, float1), float1);

Given an expression such as

   z * w + k * (1 - x)

the tricky part is to verify that either z or w is equal to x
(otherwise, it's not a valid lerp).  We solve this problem using COST
actions and user state.


   %{
       typedef struct
       {
           node_t *a;
	   node_t *b;
       } mul_kids_t;
   %}

   %state <char>       use
   %state <node_t *>   sub_node
   %state <mul_kids_t> mul_node

   %%

   float1: ADD(lerp1, lerp2) "_UST($1)->use ? 0 : MAX_COST"	
       COST
       {
           _UST($1)->use =
	         is_equal(_UST($2)->mul_node.a,
	                  _UST($3)->sub_node)
              || is_equal(_UST($2)->mul_node.b,
	                  _UST($3)->sub_node); 
       }
       ;
       
   float1: ADD(lerp2, lerp1) "_UST($1)->use ? 0 : MAX_COST"
       COST
       {
           _UST($1)->use =
	         is_equal(_UST($3)->mul_node.a,
	                  _UST($2)->sub_node)
              || is_equal(_UST($3)->mul_node.b,
	                  _UST($2)->sub_node);        
       }
       ;

   lerp1: MUL(float1, float1) "0"
       COST
       {
           /* store both MUL kids */
	   _UST($1)->mul_node.a = $2;
	   _UST($1)->mul_node.b = $3;
       }
       ;

   lerp2: MUL(float1, SUB(const_one, float1)) "0"
       COST
       {
           /* store right child of SUB */
           _UST($1)->sub_node = $5;
       }
       ;
       
   lerp2: MUL(SUB(const_one, float1), float1) "0"
       COST
       {
           /* store right child of SUB */
           _UST($1)->sub_node = $4;
       }
       ;

The overall idea is to store the relevant nodes and pass this
information back up to the higher-level rules where a comparison can
be made.  Remember that a COST action for a rule is executed before
the cost expression for that rule is evaluated.
			     
----------------------------------------------------------------------

Comments and Whitespace

lburg2 is more flexible with regards to comments and whitespace than
lburg1.  For example, the following rule declarations are equivalent:

    node: MOV(node) "1" POST { $1->value = $2->value; };

or

    node: MOV(node) "1"
        POST {
            $1->value = $2->value;
        }
    ;

or

    node
 :
              MOV(
         node)

                           "1"

  {    POST

               {
    $1->value
 =


            $2->value; }}
       ;

Obviously, the last example isn't pretty to look at, but it's
syntactically equivalent to the first two.

                             ***

lburg1 treats lines beginning with # as a comment.  lburg2 continues
to support this mechanism, but also supports C and C++ style comments.
Recall that in order to use '#' to indicate the beginning of a
one-line comment, the '#' symbol must be the first character of the
line.

examples:

    node: ADD(node, node) "1" // this is a cost of 1
        // postorder traversal action
        POST
        {
            $1->value = $2->value + $3->value;
        };

	// commented-out DEBUG action
        /*
        DEBUG
        {
            printf("Found ADD node.\n");
        }
        */
    ;   

#   this rule is commented out
#
#   node: SUB(node, node) "1"

    // this rule is commented out too;
    // the double-slash doesn't need to be at
    // the beginning of the line, though
    //
    // node: MUL(node, node) "1"

Anything contained within a comment is ignored.

------------------------------------------------------------

IMPLEMENTATION NOTES

- The lburg2 scanner uses flex instead of lburg1's hand-coded scanner.
  This makes lburg more flexible and easier to maintain.  The flex
  rules are defined in lburg_scan2.l.

- The grammar file gram2.y has been revised.  There is some additional
  code to handle bookkeeping tasks, such as storing tree lists and
  code blocks.

- lburg2 emits each rule's action as a function.  The function's name
  begins with an underscore and contains both the rule number and the
  action label.  This is an attempt to avoid namespace clashes.

- lburg2 emits a rule table indexed by rule number and action label.
  Each label is emitted as an enumerated constant.  Each entry in the
  rule table contains a function pointer (a pointer to a specific
  rule's action).

- lburg2 emits a function _action that looks up a function in the rule
  table and executes it (unless the entry in the table is NULL).

- gram2.y and lburg_scan2.l are hacked slightly to allow line-based
  sections and arbitrary whitespace.  For example, the terminal
  declarations are line-based, but the rule section is not.  In
  particular, the {R_PPERCENT} rule for the scanner knows that after
  the first %% encountered, we don't need to take care of newlines
  anymore.

------------------------------------------------------------

Revisions

8-3-2001
Added _COST_UST documentation.
 -ec

8-2-2001
Added new documentation for user state and COST actions.
 -ec

7-27-2001
Added explanation of NTH_CHILD and some cost expression warnings.
 -ec
 
7-19-2001
Added section on packing opcode + optype for rule flexibility.
Clarified .bg2 vs .bg files.
 -ec

7-18-2001
Revised lburg2 grammar and comment docs.
 -ec

7-17-2001
Initial.
 -ec