blob: 3dc67be3176bba098fad8d0b3dfa7c05437db449 [file] [log] [blame]
 \documentstyle[11pt,fullpage]{article} \begin{document} \def\AddSpace#1{\ifcat#1a\ \fi#1} % if next is a letter, add a space \def\YACC#1{{\sc Yacc}\AddSpace#1} \def\TWIG#1{{\sc Twig}\AddSpace#1} \def\PROG#1{{\sc Burg}\AddSpace#1} \def\PARSER#1{{\sc Burm}\AddSpace#1} \def\CODEGEN#1{{\sc Codegen}\AddSpace#1} \title{{\sc Burg} --- Fast Optimal Instruction Selection and Tree Parsing} \author{ Christopher W. Fraser \\ AT\&T Bell Laboratories \\ 600 Mountain Avenue 2C-464 \\ Murray Hill, NJ 07974-0636 \\ {\tt cwf@research.att.com} \and Robert R. Henry \\ Tera Computer Company \\ 400 N. 34th St., Suite 300 \\ Seattle, WA 98103-8600 \\ {\tt rrh@tera.com} \and Todd A. Proebsting \\ Dept. of Computer Sciences \\ University of Wisconsin \\ Madison, WI 53706 \\ {\tt todd@cs.wisc.edu} } \date{December 1991} \maketitle \bibliographystyle{alpha} \newcommand\term[1]{{\it #1}} \newcommand\secref[1]{\S\ref{#1}} \newcommand\figref[1]{Figure~\ref{#1}} % % rationale table making % {\catcode\^^M=13 \gdef\Obeycr{\catcode\^^M=13 \def^^M{\\}}% \gdef\Restorecr{\catcode\^^M=5 }} % % % for printing out options % \newcommand\option[1]{% #1=option character {\tt -#1}% } \newcommand\var[1]{% {\tt #1}% } \section{Overview} \PROG is a program that generates a fast tree parser using BURS (Bottom-Up Rewrite System) technology. It accepts a cost-augmented tree grammar and emits a C program that discovers in linear time an optimal parse of trees in the language described by the grammar. \PROG has been used to construct fast optimal instruction selectors for use in code generation. \PROG addresses many of the problems addressed by {\sc Twig}~\cite{aho-twig-toplas,appel-87}, but it is somewhat less flexible and much faster. \PROG is available via anonymous \var{ftp} from \var{kaese.cs.wisc.edu}. The compressed \var{shar} file \var{pub/burg.shar.Z} holds the complete distribution. This document describes only that fraction of the BURS model that is required to use \PROG. Readers interested in more detail might start with Reference~\cite{balachandran-complang}. Other relevant documents include References~\cite{kron-phd,hoffmann-jacm,hatcher-popl,chase-popl,pelegri-popl,pelegri-phd,wilhelm-tr,henry-budp,fraser-henry-spe-91,proebsting-91}. \section{Input} \PROG accepts a tree grammar and emits a BURS tree parser. \figref{fig-tree-grammar} shows a sample grammar that implements a very simple instruction selector. \begin{figure} \begin{verbatim} %{ #define NODEPTR_TYPE treepointer #define OP_LABEL(p) ((p)->op) #define LEFT_CHILD(p) ((p)->left) #define RIGHT_CHILD(p) ((p)->right) #define STATE_LABEL(p) ((p)->state_label) #define PANIC printf %} %start reg %term Assign=1 Constant=2 Fetch=3 Four=4 Mul=5 Plus=6 %% con: Constant = 1 (0); con: Four = 2 (0); addr: con = 3 (0); addr: Plus(con,reg) = 4 (0); addr: Plus(con,Mul(Four,reg)) = 5 (0); reg: Fetch(addr) = 6 (1); reg: Assign(addr,reg) = 7 (1); \end{verbatim} \caption{A Sample Tree Grammar\label{fig-tree-grammar}} \end{figure} \PROG grammars are structurally similar to \YACC's. Comments follow C conventions. Text between \var{\%\{}'' and \var{\%\}}'' is called the \term{configuration section}; there may be several such segments. All are concatenated and copied verbatim into the head of the generated parser, which is called \PARSER. Text after the second \var{\%\%}'', if any, is also copied verbatim into \PARSER, at the end. The configuration section configures \PARSER for the trees being parsed and the client's environment. This section must define \var{NODEPTR\_TYPE} to be a visible typedef symbol for a pointer to a node in the subject tree. \PARSER invokes \var{OP\_LABEL(p)}, \var{LEFT\_CHILD(p)}, and \var{RIGHT\_CHILD(p)} to read the operator and children from the node pointed to by \var{p}. It invokes \var{PANIC} when it detects an error. If the configuration section defines these operations as macros, they are implemented in-line; otherwise, they must be implemented as functions. The section on diagnostics elaborates on \var{PANIC}. \PARSER computes and stores a single integral \term{state} in each node of the subject tree. The configuration section must define a macro \var{STATE\_LABEL(p)} to access the state field of the node pointed to by \var{p}. A macro is required because \PROG uses it as an lvalue. A C \var{short} is usually the right choice; typical code generation grammars require 100--1000 distinct state labels. The tree grammar follows the configuration section. \figref{fig-grammar-grammar} gives an EBNF grammar for \PROG tree grammars. \begin{figure} \begin{verbatim} grammar: {dcl} '%%' {rule} dcl: '%start' Nonterminal dcl: '%term' { Identifier '=' Integer } rule: Nonterminal ':' tree '=' Integer cost ';' cost: /* empty */ cost: '(' Integer { ',' Integer } ')' tree: Term '(' tree ',' tree ')' tree: Term '(' tree ')' tree: Term tree: Nonterminal \end{verbatim} \caption{EBNF Grammar for Tree Grammars for \PROG\ \label{fig-grammar-grammar}} \end{figure} Comments, the text between \var{\%\{}'' and \var{\%\}}'', and the text after the optional second \var{\%\%}'' are treated lexically, so the figure omits them. In the EBNF grammar, quoted text must appear literally, \var{Nonterminal} and \var{Integer} are self-explanatory, and \var{Term} denotes an identifier previously declared as a terminal. {\tt\{$X$\}} denotes zero or more instances of $X$. Text before the first \var{\%\%}'' declares the start symbol and the terminals or operators in subject trees. All terminals must be declared; each line of such declarations begins with \var{\%term}. Each terminal has fixed arity, which \PROG infers from the rules using that terminal. \PROG restricts terminals to have at most two children. Each terminal is declared with a positive, unique, integral \term{external symbol number} after a \var{=}''. \var{OP\_LABEL(p)} must return the valid external symbol number for \var{p}. Ideally, external symbol numbers form a dense enumeration. Non-terminals are not declared, but the start symbol may be declared with a line that begins with \var{\%start}. Text after the first \var{\%\%}'' declares the rules. A tree grammar is like a context-free grammar: it has rules, non-terminals, terminals, and a special start non-terminal. The right-hand side of a rule, called the \term{pattern}, is a tree. Tree patterns appear in prefix parenthesized form. Every non-terminal denotes a tree. A chain rule is a rule whose pattern is another non-terminal. If no start symbol is declared, \PROG uses the non-terminal defined by the first rule. \PROG needs a single start symbol; grammars for which it is natural to use multiple start symbols must be augmented with an artificial start symbol that derives, with zero cost, the grammar's natural start symbols. \PARSER will automatically select one that costs least for any given tree. \PROG accepts no embedded semantic actions like \YACC's, because no one format suited all intended applications. Instead, each rule has a positive, unique, integral \term{external rule number}, after the pattern and preceded by a \var{=}''. Ideally, external rule numbers form a dense enumeration. \PARSER uses these numbers to report the matching rule to a user-supplied routine, which must implement any desired semantic action; see below. Humans may select these integers by hand, but \PROG is intended as a \term{server} for building BURS tree parsers. Thus some \PROG clients will consume a richer description and translate it into \PROG's simpler input. Rules end with a vector of non-negative, integer costs, in parentheses and separated by commas. If the cost vector is omitted, then all elements are assumed to be zero. \PROG retains only the first four elements of the list. The cost of a derivation is the sum of the costs for all rules applied in the derivation. Arithmetic on cost vectors treats each member of the vector independently. The tree parser finds the cheapest parse of the subject tree. It breaks ties arbitrarily. By default, \PROG uses only the \term{principal cost} of each cost vector, which defaults to the first element, but options described below provide alternatives. \section{Output} \PARSER traverses the subject tree twice. The first pass or \term{labeller} runs bottom-up and left-to-right, visiting each node exactly once. Each node is labeled with a state, a single number that encodes all full and partial optimal pattern matches viable at that node. The second pass or \term{reducer} traverses the subject tree top-down. The reducer accepts a tree node's state label and a \term{goal} non-terminal --- initially the root's state label and the start symbol --- which combine to determine the rule to be applied at that node. By construction, the rule has the given goal non-terminal as its left-hand side. The rule's pattern identifies the subject subtrees and goal non-terminals for all recursive visits. Here, a subtree'' is not necessarily an immediate child of the current node. Patterns with interior operators cause the reducer to skip the corresponding subject nodes, so the reducer may proceed directly to grandchildren, great-grandchildren, and so on. On the other hand, chain rules cause the reducer to revisit the current subject node, with a new goal non-terminal, so \term{x} is also regarded as a subtree of \term{x}. As the reducer visits (and possibly revisits) each node, user-supplied code implements semantic action side effects and controls the order in which subtrees are visited. The labeller is self-contained, but the reducer combines code from \PROG with code from the user, so \PARSER does not stand alone. The \PARSER that is generated by \PROG provides primitives for labelling and reducing trees. These mechanisms are a compromise between expressibility, abstraction, simplicity, flexibility and efficiency. Clients may combine primitives into labellers and reducers that can traverse trees in arbitrary ways, and they may call semantic routines when and how they wish during traversal. Also, \PROG generates a few higher level routines that implement common combinations of primitives, and it generates mechanisms that help debug the tree parse. \PROG generates the labeller as a function named \var{burm\_label} with the signature \begin{verbatim} extern int burm_label(NODEPTR_TYPE p); \end{verbatim} It labels the entire subject tree pointed to by \var{p} and returns the root's state label. State zero labels unmatched trees. The trees may be corrupt or merely inconsistent with the grammar. The simpler \var{burm\_state} is \var{burm\_label} without the code to traverse the tree and to read and write its fields. It may be used to integrate labelling into user-supplied traversal code. A typical signature is \begin{verbatim} extern int burm_state(int op, int leftstate, int rightstate); \end{verbatim} It accepts an external symbol number for a node and the labels for the node's left and right children. It returns the state label to assign to that node. For unary operators, the last argument is ignored; for leaves, the last two arguments are ignored. In general, \PROG generates a \var{burm\_state} that accepts the maximum number of child states required by the input grammar. For example, if the grammar includes no binary operators, then \var{burm\_state} will have the signature \begin{verbatim} extern int burm_state(int op, int leftstate); \end{verbatim} This feature is included to permit future expansion to operators with more than two children. The user must write the reducer, but \PARSER writes code and data that help. Primary is \begin{verbatim} extern int burm_rule(int state, int goalnt); \end{verbatim} which accepts a tree's state label and a goal non-terminal and returns the external rule number of a rule. The rule will have matched the tree and have the goal non-terminal on the left-hand side; \var{burm\_rule} returns zero when the tree labelled with the given state did not match the goal non-terminal. For the initial, root-level call, \var{goalnt} must be one, and \PARSER exports an array that identifies the values for nested calls: \begin{verbatim} extern short *burm_nts[] = { ... }; \end{verbatim} is an array indexed by external rule numbers. Each element points to a zero-terminated vector of short integers, which encode the goal non-terminals for that rule's pattern, left-to-right. The user needs only these two externals to write a complete reducer, but a third external simplifies some applications: \begin{verbatim} extern NODEPTR_TYPE *burm_kids(NODEPTR_TYPE p, int eruleno, NODEPTR_TYPE kids[]); \end{verbatim} accepts the address of a tree \var{p}, an external rule number, and an empty vector of pointers to trees. The procedure assumes that \var{p} matched the given rule, and it fills in the vector with the subtrees (in the sense described above) of \var{p} that must be reduced recursively. \var{kids} is returned. It is not zero-terminated. The simple user code below labels and then fully reduces a subject tree; the reducer prints the tree cover. \var{burm\_string} is defined below. \begin{verbatim} parse(NODEPTR_TYPE p) { burm_label(p); /* label the tree */ reduce(p, 1, 0); /* and reduce it */ } reduce(NODEPTR_TYPE p, int goalnt, int indent) { int eruleno = burm_rule(STATE_LABEL(p), goalnt); /* matching rule number */ short *nts = burm_nts[eruleno]; /* subtree goal non-terminals */ NODEPTR_TYPE kids[10]; /* subtree pointers */ int i; for (i = 0; i < indent; i++) printf("."); /* print indented ... */ printf("%s\n", burm_string[eruleno]); /* ... text of rule */ burm_kids(p, eruleno, kids); /* initialize subtree pointers */ for (i = 0; nts[i]; i++) /* traverse subtrees left-to-right */ reduce(kids[i], nts[i], indent+1); /* and print them recursively */ } \end{verbatim} The reducer may recursively traverse subtrees in any order, and it may interleave arbitrary semantic actions with recursive traversals. Multiple reducers may be written, to implement multi-pass algorithms or independent single-pass algorithms. For each non-terminal $x$, \PROG emits a preprocessor directive to equate \var{burm\_}$x$\var{\_NT} with $x$'s integral encoding. It also defines a macro \var{burm\_}$x$\var{\_rule(a)} that is equivalent to \var{burm\_rule(a,}$x$\var{)}. For the grammar in \figref{fig-tree-grammar}, \PROG emits \begin{verbatim} #define burm_reg_NT 1 #define burm_con_NT 2 #define burm_addr_NT 3 #define burm_reg_rule(a) ... #define burm_con_rule(a) ... #define burm_addr_rule(a) ... \end{verbatim} Such symbols are visible only to the code after the second `\var{\%\%}''. If the symbols \var{burm\_}$x$\var{\_NT} are needed elsewhere, extract them from the \PARSER source. The \option{I} option directs \PROG to emit an encoding of the input that may help the user produce diagnostics. The vectors \begin{verbatim} extern char *burm_opname[]; extern char burm_arity[]; \end{verbatim} hold the name and number of children, respectively, for each terminal. They are indexed by the terminal's external symbol number. The vectors \begin{verbatim} extern char *burm_string[]; extern short burm_cost[][4]; \end{verbatim} hold the text and cost vector for each rule. They are indexed by the external rule number. The zero-terminated vector \begin{verbatim} extern char *burm_ntname[]; \end{verbatim} is indexed by \var{burm\_}$x$\var{\_NT} and holds the name of non-terminal $x$. Finally, the procedures \begin{verbatim} extern int burm_op_label(NODEPTR_TYPE p); extern int burm_state_label(NODEPTR_TYPE p); extern NODEPTR_TYPE burm_child(NODEPTR_TYPE p, int index); \end{verbatim} are callable versions of the configuration macros. \var{burm\_child(p,0)} implements \var{LEFT\_CHILD(p)}, and \var{burm\_child(p,1)} implements \var{RIGHT\_CHILD(p)}. A sample use is the grammar-independent expression \var{burm\_opname[burm\_op\_label(p)]}, which yields the textual name for the operator in the tree node pointed to by \var{p}. A complete tree parser can be assembled from just \var{burm\_state}, \var{burm\_rule}, and \var{burm\_nts}, which use none of the configuration section except \var{PANIC}. The generated routines that use the rest of the configuration section are compiled only if the configuration section defines \var{STATE\_LABEL}, so they can be omitted if the user prefers to hide the tree structure from \PARSER. This course may be wise if, say, the tree structure is defined in a large header file with symbols that might collide with \PARSER's. \PARSER selects an optimal parse without dynamic programming at compile time~\cite{aho-johnson-dp-classic}. Instead, \PROG does the dynamic programming at compile-compile time, as it builds \PARSER. Consequently, \PARSER parses quickly. Similar labellers have taken as few as 15 instructions per node, and reducers as few as 35 per node visited~\cite{fraser-henry-spe-91}. \section{Debugging} \PARSER invokes \var{PANIC} when an error prevents it from proceeding. \var{PANIC} has the same signature as \var{printf}. It should pass its arguments to \var{printf} if diagnostics are desired and then either abort (say via \var{exit}) or recover (say via \var{longjmp}). If it returns, \PARSER aborts. Some errors are not caught. \PROG assumes a robust preprocessor, so it omits full consistency checking and error recovery. \PROG constructs a set of states using a closure algorithm like that used in LR table construction. \PROG considers all possible trees generated by the tree grammar and summarizes infinite sets of trees with finite sets. The summary records the cost of those trees but actually manipulates the differences in costs between viable alternatives using a dynamic programming algorithm. Reference~\cite{henry-budp} elaborates. Some grammars derive trees whose optimal parses depend on arbitrarily distant data. When this happens, \PROG and the tree grammar \term{cost diverge}, and \PROG attempts to build an infinite set of states; it first thrashes and ultimately exhausts memory and exits. For example, the tree grammar in \figref{fig-diverge-grammar} \begin{figure} \begin{verbatim} %term Const=17 RedFetch=20 GreenFetch=21 Plus=22 %% reg: GreenFetch(green_reg) = 10 (0); reg: RedFetch(red_reg) = 11 (0); green_reg: Const = 20 (0); green_reg: Plus(green_reg,green_reg) = 21 (1); red_reg: Const = 30 (0); red_reg: Plus(red_reg,red_reg) = 31 (2); \end{verbatim} \caption{A Diverging Tree Grammar\label{fig-diverge-grammar}} \end{figure} diverges, since non-terminals \var{green\_reg} and \var{red\_reg} derive identical infinite trees with different costs. If the cost of rule 31 is changed to 1, then the grammar does not diverge. Practical tree grammars describing instruction selection do not cost-diverge because infinite trees are derived from non-terminals that model temporary registers. Machines can move data between different types of registers for a small bounded cost, and the rules for these instructions prevent divergence. For example, if \figref{fig-diverge-grammar} included rules to move data between red and green registers, the grammar would not diverge. If a bonafide machine grammar appears to make \PROG loop, try a host with more memory. To apply \PROG to problems other than instruction selection, be prepared to consult the literature on cost-divergence~\cite{pelegri-phd}. \section{Running \PROG\ }\label{sec-man-page} \PROG reads a tree grammar and writes a \PARSER in C. \PARSER can be compiled by itself or included in another file. When suitably named with the \option{p} option, disjoint instances of \PARSER should link together without name conflicts. The command: \begin{flushleft} \var{burg} [ {\it arguments} ] [ {\it file} ] \end{flushleft} invokes \PROG. If a {\it file} is named, \PROG expects its grammar there; otherwise it reads the standard input. The options include: \def\Empty{} % \newcommand\odescr[2]{% #1=option character, #2=optional argument \gdef\Arg2{#2}% \item[\option{#1}\ifx\Arg2\Empty\else{{\it #2}}\fi] } \begin{description} % \odescr{c}{} $N$ Abort if any relative cost exceeds $N$, which keeps \PROG from looping on diverging grammars. Several references~\cite{pelegri-popl,henry-budp,balachandran-complang,proebsting-91} explain relative costs. % \odescr{d}{} Report a few statistics and flag unused rules and terminals. % \odescr{o}{} {\it file} Write parser into {\it file}. Otherwise it writes to the standard output. % \odescr{p}{} {\it prefix} Start exported names with {\it prefix}. The default is \var{burm}. % \odescr{t}{} Generates smaller tables faster, but all goal non-terminals passed to \var{burm\_rule} must come from an appropriate \var{burm\_nts}. Using \var{burm\_}$x$\var{\_NT} instead may give unpredictable results. % \odescr{I}{} Emit code for \var{burm\_arity}, \var{burm\_child}, \var{burm\_cost}, \var{burm\_ntname}, \var{burm\_op\_label}, \var{burm\_opname}, \var{burm\_state\_label}, and \var{burm\_string}. % \odescr{O}{} $N$ Change the principal cost to $N$. Elements of each cost vector are numbered from zero. % \odescr{=}{} Compare costs lexicographically, using all costs in the given order. This option slows \PROG and may produce a larger parser. Increases range from small to astronomical. \end{description} \section{Acknowledgements} The first \PROG was adapted by the second author from his \CODEGEN package, which was developed at the University of Washington with partial support from NSF Grant CCR-88-01806. It was unbundled from \CODEGEN with the support of Tera Computer. The current \PROG was written by the third author with the support of NSF grant CCR-8908355. The interface, documentation, and testing involved all three authors. Comments from a large group at the 1991 Dagstuhl Seminar on Code Generation improved \PROG's interface. Robert Giegerich and Susan Graham organized the workshop, and the International Conference and Research Center for Computer Science, Schloss Dagstuhl, provided an ideal environment for such collaboration. Beta-testers included Helmut Emmelmann, Dave Hanson, John Hauser, Hugh Redelmeier, and Bill Waite. \begin{thebibliography}{BMW87} \bibitem[AGT89]{aho-twig-toplas} Alfred~V. Aho, Mahadevan Ganapathi, and Steven W.~K. Tjiang. \newblock Code generation using tree matching and dynamic programming. \newblock {\em ACM Transactions on Programming Languages and Systems}, 11(4):491--516, October 1989. \bibitem[AJ76]{aho-johnson-dp-classic} Alfred~V. Aho and Steven~C. Johnson. \newblock Optimal code generation for expression trees. \newblock {\em Journal of the ACM}, 23(3):458--501, July 1976. \bibitem[App87]{appel-87} Andrew~W. Appel. \newblock Concise specification of locally optimal code generators. \newblock Technical report CS-TR-080-87, Princeton University, 1987. \bibitem[BDB90]{balachandran-complang} A.~Balachandran, D.~M. Dhamdhere, and S.~Biswas. \newblock Efficient retargetable code generation using bottom-up tree pattern matching. \newblock {\em Computer Languages}, 15(3):127--140, 1990. \bibitem[BMW87]{wilhelm-tr} J\"{u}rgen B\"{o}rstler, Ulrich M\"{o}nche, and Reinhard Wilhelm. \newblock Table compression for tree automata. \newblock Technical Report Aachener Informatik-Berichte No. 87-12, RWTH Aachen, Fachgruppe Informatik, Aachen, Fed. Rep. of Germany, 1987. \bibitem[Cha87]{chase-popl} David~R. Chase. \newblock An improvement to bottom up tree pattern matching. \newblock {\em Fourteenth Annual ACM Symposium on Principles of Programming Languages}, pages 168--177, January 1987. \bibitem[FH91]{fraser-henry-spe-91} Christopher~W. Fraser and Robert~R. Henry. \newblock Hard-coding bottom-up code generation tables to save time and space. \newblock {\em Software---Practice\&Experience}, 21(1):1--12, January 1991. \bibitem[HC86]{hatcher-popl} Philip~J. Hatcher and Thomas~W. Christopher. \newblock High-quality code generation via bottom-up tree pattern matching. \newblock {\em Thirteenth Annual ACM Symposium on Principles of Programming Languages}, pages 119--130, January 1986. \bibitem[Hen89]{henry-budp} Robert~R. Henry. \newblock Encoding optimal pattern selection in a table-driven bottom-up tree-pattern matcher. \newblock Technical Report 89-02-04, University of Washington Computer Science Department, Seattle, WA, February 1989. \bibitem[HO82]{hoffmann-jacm} Christoph Hoffmann and Michael~J. O'Donnell. \newblock Pattern matching in trees. \newblock {\em Journal of the ACM}, 29(1):68--95, January 1982. \bibitem[Kro75]{kron-phd} H.~H. Kron. \newblock {\em Tree Templates and Subtree Transformational Grammars}. \newblock PhD thesis, UC Santa Cruz, December 1975. \bibitem[PL87]{pelegri-phd} Eduardo Pelegri-Llopart. \newblock {\em Tree Transformations in Compiler Systems}. \newblock PhD thesis, UC Berkeley, December 1987. \bibitem[PLG88]{pelegri-popl} Eduardo Pelegri-Llopart and Susan~L. Graham. \newblock Optimal code generation for expression trees: An application of {BURS} theory. \newblock {\em Fifteenth Annual ACM Symposium on Principles of Programming Languages}, pages 294--308, January 1988. \bibitem[Pro91]{proebsting-91} Todd~A. Proebsting. \newblock Simple and efficient {BURS} table generation. \newblock Technical report, Department of Computer Sciences, University of Wisconsin, 1991. \end{thebibliography} \end{document}