Installation Procedure
----------------------
To install twig, you must decide in which directories to place:

(1) the twig compiler binary, and
(2) the twig template files.

Once you have made these two decisions, you should edit the mkfile and twig.y.
The installation can then be completed by typing:

	mk install

Once a user has written a twig specification, the command twig is used to
compile it.  The compilation creates two files called walker.c,
containing several subroutines, and symbols.h, containing definitions.
Walker.c is compiled and linked with the rest of the user program, and
tree matching occurs when the user's program calls a subroutine called _match.
More details about twig specifications, and how to interface to the
subroutines in walker.c is given in the ``Twig Reference Manual'', AT&T Bell
Laboratories, Computing Science Technical Report #120.

Addendum to the ``Twig Reference Manual''
-----------------------------------------

1.	In a node declaration, the user can override the automatic numbering
	of a node id by expliciting assigning a number using the ``= int''
	construct.  However, the user must then assign a number to all
	of the node ids.  In other words, the user must either assign
	numbers to each of the node ids, or to none of them.  The ids must
	have unique numbers.

2.	The default action of executing the labelled leaves from
	right to left is inadequate.  ``Execution,'' as used here, is in
	the sense as described in the ``Twig Reference Manual.''  Although
	one could simulate any execution order by using a top-down rule, and
	explicitly requesting the execution of labelled leaves with the tDO
	macro, it is tedious to do so.  For example, implementing a Sethi-Ullman
	style register allocator  in such a fashion is extremely awkward.
	To alleviate this tedium, reordering scheme has been proposed, and
	implemented by Andrew Appel of Princeton University.  It is included
	in this version of twig.

	A function, ``_do'' performs the execution of the matches.  This
	function is part of the walker.c file generated by twig.  In versions
	of the walker without reordering, _do performs the call:

		_evalleaves(winner->lleaves);

	where winner->lleaves are the labelled leaves of the winning match.
	Lleaves has type ``__match *[], '' and is a NULL terminated sequence
	of matches for the labelled leaves in left to right order.  Calling
	tDO with an element of lleaves executes the match associated with
	the labelled leaf.

	Reordering is accomplished by changing the call to _evalleaves with
	the statement:

		REORDER(winner->lleaves);

	REORDER is a macro, or function defined by the user that may execute
	the leaves in any order.  If the user does not define REORDER then
	twig will generate a default, which is to call _evalleaves.

	For example, if the user wishes to execute the leaves in the order of
	decreasing cost, the following definition could be used.

	prologue {
	...
	#define REORDER(list)	reorder(list)
	...
	}

	...

	insert {

	reorder(list)
		__match **list;
	{
		int i, j, n;
		__match *index[16];

		/* copy list into index */
		for(n=0; list[n]; n++) index[n] = list[n];

		/* insertion sort */
		for(j=0;j<n;j++)
		    for(i=j; i>0; i--)
			if(index[i]->cost > index[i-1]->cost) {
				/* swap them */
				__match *temp = index[i];
				index[i] = index[i-1]; index[i-1] = p;
			}

		/* now execute */
		for(j=0;j<n;j++)
			tDO(index[j]);
	}

	}


3.	In a top-down rule, there is often a desire to execute all the
	labelled leaves after performing some preparatory actions.  This
	could be done by saying

		tDO($%1$); tDO($%2$); ...

	However, the short hand notation, ``EVAL;'' provides the same function.
	
4.	In the previous version of twig, Walker.c had a reference to
	walker.h.  Hence the user had to compile walker.c with the command:

		cc -Iinclude_dir -c walker.c

	where include_dir was the directory containing walker.h.
	The reference to walker.h has been eliminated by inserting walker.h
	into all the template files that could generate walker.c.
	Therefore the new compile command is:

		cc -c walker.c

5.	Twig assigns numbers to the node symbols, which are used to identify
	nodes to the tree matcher.  In the previous version of twig, the
	tree matcher actually recognized ``M_NODE|number'' as the value
	assigned to the node symbol rather than just plain ``number.''
	This was completely undocumented.  The current version fixed the
	tree matcher to recognize ``number'' as the correct value associated
	with a node symbol.

6.	Twig now uses dynamic initialization of costs rather than static
	initialization.  This permits the user to declare COST as structure.

7.	Many cost metrics used in twig programs are additive.  That is,
	the cost of a match is some constant cost plus the sum of the
	costs of the matches at the labelled leaves.  The macros ZEROCOST, and
	ADDCOST provide an easy way to implement this.  For example, if costs
	are integers, then the definition

	#define ZEROCOST	1
	#define ADDCOST(accum,y)	(accum) += (y)

	would cause twig to generate, for rules without a cost part, code that
	calculate the default cost as one plus the sum of the costs of the
	matches at the labelled leaves.

	ZEROCOST, and ADDCOST must both be defined, if the above facility is
	to be used.  DEFAULT_COST must not be defined when ADDCOST is defined.

8. Changes made by Keutzer (allegra!keutzer) and Appel (research!appel)
	
	modifications by keutzer:
	
	char c ->int c 
	all over lex.c
	
	varargs added in _mtG in walker.c 
		may be too expensive for some people. 
		code is not portable to a SUN4 without it however.
	
	"short int"'s were changed to "short"'s for UTS compatability.
	
	The  NODE struct pointed to by a NODEPTR now needs a "mark" field.
	 
	A printTree(NODEPTR n) routine must also be supplied by the  user.
	 
	If you were using the values of nodes in your symbols.h file
	then the command
	        cc -g -c -DDUMPNAMES sym.c
	should be used to compile sym.c.

9. Changes made by smd
	now all in ansi C.
	stdarg used for all error printing routines.
	some dead definitions in common.h removed.

	the -s flag does what compiling with -DDUMPNAMES claimed to do
	but didn't.

	walker.c1 in ansi C.
	_mtG uses stdarg now.

	bug in machineGen2 fixed:
		if(MI_BRANCH(mach->inp.value)&&gen_table2) {
		used to have mp, which was null, instead of mach.