Move support/tools/* back into utils

llvm-svn: 8875

35 files changed, 6455 insertions, 0 deletions

diff --git a/llvm/utils/Burg/COPYRIGHT b/llvm/utils/Burg/COPYRIGHT
new file mode 100644
index 00000000000..1de0aad6f2f
--- /dev/null
+++ b/llvm/utils/Burg/COPYRIGHT
@@ -0,0 +1,13 @@
+Copyright (C) 1991 Todd A. Proebsting
+All Rights Reserved.
+
+This software is in the public domain.  You may use and copy this material
+freely. This privilege extends to modifications, although any modified
+version of this system given to a third party should clearly identify your
+modifications as well as the original source.
+
+The responsibility for the use of this material resides entirely with you.
+We make no warranty of any kind concerning this material, nor do we make
+any claim as to the suitability of BURG for any application.  This software
+is experimental in nature and there is no written or implied warranty.  Use
+it at your own risk.
diff --git a/llvm/utils/Burg/Doc/Makefile b/llvm/utils/Burg/Doc/Makefile
new file mode 100644
index 00000000000..226210d6ca4
--- /dev/null
+++ b/llvm/utils/Burg/Doc/Makefile
@@ -0,0 +1,84 @@
+# $Id$
+
+#CFLAGS	=
+#CFLAGS	= -O
+#CFLAGS	= -O -DNOLEX
+CFLAGS	= -g -DDEBUG
+#CFLAGS	= -g -DNOLEX -DDEBUG
+
+SRCS = \
+	be.c \
+	burs.c \
+	closure.c \
+	delta.c \
+	fe.c \
+	item.c \
+	lex.c \
+	list.c \
+	main.c \
+	map.c \
+	nonterminal.c \
+	operator.c \
+	pattern.c \
+	plank.c \
+	queue.c \
+	rule.c \
+	string.c \
+	symtab.c \
+	table.c \
+	trim.c \
+	zalloc.c
+
+BU_OBJS = \
+	burs.o \
+	closure.o \
+	delta.o \
+	item.o \
+	list.o \
+	map.o \
+	nonterminal.o \
+	operator.o \
+	pattern.o \
+	queue.o \
+	rule.o \
+	table.o \
+	trim.o \
+	zalloc.o
+
+FE_OBJS = \
+	be.o \
+	fe.o \
+	lex.o \
+	main.o \
+	plank.o \
+	string.o \
+	symtab.o \
+	y.tab.o
+
+all: test
+
+burg: $(BU_OBJS) $(FE_OBJS)
+	$(CC) -o burg $(CFLAGS) $(BU_OBJS) $(FE_OBJS)
+
+y.tab.c y.tab.h: gram.y
+	yacc -d gram.y
+
+clean:
+	rm -f *.o y.tab.h y.tab.c core burg *.aux *.log *.dvi sample sample.c tmp
+
+$(FE_OBJS):	b.h
+$(BU_OBJS):	b.h
+$(FE_OBJS):	fe.h
+
+lex.o:	y.tab.h
+
+doc.dvi: doc.tex
+	latex doc; latex doc
+
+test: burg sample.gr
+	./burg -I     <sample.gr   >sample.c && cc $(CFLAGS) -o sample sample.c && ./sample
+	./burg -I      sample.gr   >tmp && cmp tmp sample.c
+	./burg -I     <sample.gr -o tmp && cmp tmp sample.c
+	./burg -I      sample.gr -o tmp && cmp tmp sample.c
+	./burg -I -O0 <sample.gr   >tmp && cmp tmp sample.c
+	./burg -I -=  <sample.gr   >tmp && cmp tmp sample.c
diff --git a/llvm/utils/Burg/Doc/doc.aux b/llvm/utils/Burg/Doc/doc.aux
new file mode 100644
index 00000000000..0f7c13f0208
--- /dev/null
+++ b/llvm/utils/Burg/Doc/doc.aux
@@ -0,0 +1,50 @@
+\relax 
+\bibstyle{alpha}
+\citation{aho-twig-toplas}
+\citation{appel-87}
+\citation{balachandran-complang}
+\citation{kron-phd}
+\citation{hoffmann-jacm}
+\citation{hatcher-popl}
+\citation{chase-popl}
+\citation{pelegri-popl}
+\citation{pelegri-phd}
+\citation{wilhelm-tr}
+\citation{henry-budp}
+\citation{fraser-henry-spe-91}
+\citation{proebsting-91}
+\@writefile{toc}{\contentsline {section}{\numberline {1}Overview}{1}}
+\@writefile{toc}{\contentsline {section}{\numberline {2}Input}{1}}
+\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces A Sample Tree Grammar}}{2}}
+\newlabel{fig-tree-grammar}{{1}{2}}
+\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces EBNF Grammar for Tree Grammars for {\sc  Burg}\ }}{3}}
+\newlabel{fig-grammar-grammar}{{2}{3}}
+\@writefile{toc}{\contentsline {section}{\numberline {3}Output}{3}}
+\citation{aho-johnson-dp-classic}
+\citation{fraser-henry-spe-91}
+\citation{henry-budp}
+\citation{pelegri-phd}
+\@writefile{toc}{\contentsline {section}{\numberline {4}Debugging}{6}}
+\@writefile{toc}{\contentsline {section}{\numberline {5}Running {\sc  Burg}\ }{6}}
+\newlabel{sec-man-page}{{5}{6}}
+\citation{pelegri-popl}
+\citation{henry-budp}
+\citation{balachandran-complang}
+\citation{proebsting-91}
+\@writefile{lof}{\contentsline {figure}{\numberline {3}{\ignorespaces A Diverging Tree Grammar}}{7}}
+\newlabel{fig-diverge-grammar}{{3}{7}}
+\@writefile{toc}{\contentsline {section}{\numberline {6}Acknowledgements}{7}}
+\bibcite{aho-twig-toplas}{AGT89}
+\bibcite{aho-johnson-dp-classic}{AJ76}
+\bibcite{appel-87}{App87}
+\bibcite{balachandran-complang}{BDB90}
+\bibcite{wilhelm-tr}{BMW87}
+\bibcite{chase-popl}{Cha87}
+\bibcite{fraser-henry-spe-91}{FH91}
+\bibcite{hatcher-popl}{HC86}
+\bibcite{henry-budp}{Hen89}
+\bibcite{hoffmann-jacm}{HO82}
+\bibcite{kron-phd}{Kro75}
+\bibcite{pelegri-phd}{PL87}
+\bibcite{pelegri-popl}{PLG88}
+\bibcite{proebsting-91}{Pro91}
diff --git a/llvm/utils/Burg/Doc/doc.dvi b/llvm/utils/Burg/Doc/doc.dvi
new file mode 100644
index 00000000000..3211f32c96d
--- /dev/null
+++ b/llvm/utils/Burg/Doc/doc.dvi
diff --git a/llvm/utils/Burg/Doc/doc.log b/llvm/utils/Burg/Doc/doc.log
new file mode 100644
index 00000000000..a224a4edf72
--- /dev/null
+++ b/llvm/utils/Burg/Doc/doc.log
@@ -0,0 +1,157 @@
+This is TeX, Version 3.14159 (Web2C 7.3.2) (format=latex 2000.8.30)  4 JUN 2001 13:20
+**doc
+(doc.tex
+LaTeX2e <2000/06/01>
+(/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/base/latex209.def
+File: latex209.def 1998/05/13 v0.52 Standard LaTeX file
+
+
+          Entering LaTeX 2.09 COMPATIBILITY MODE
+ *************************************************************
+    !!WARNING!!    !!WARNING!!    !!WARNING!!    !!WARNING!!   
+ 
+ This mode attempts to provide an emulation of the LaTeX 2.09
+ author environment so that OLD documents can be successfully
+ processed. It should NOT be used for NEW documents!
+ 
+ New documents should use Standard LaTeX conventions and start
+ with the \documentclass command.
+ 
+ Compatibility mode is UNLIKELY TO WORK with LaTeX 2.09 style
+ files that change any internal macros, especially not with
+ those that change the FONT SELECTION or OUTPUT ROUTINES.
+ 
+ Therefore such style files MUST BE UPDATED to use
+          Current Standard LaTeX: LaTeX2e.
+ If you suspect that you may be using such a style file, which
+ is probably very, very old by now, then you should attempt to
+ get it updated by sending a copy of this error message to the
+ author of that file.
+ *************************************************************
+
+\footheight=\dimen102
+\@maxsep=\dimen103
+\@dblmaxsep=\dimen104
+\@cla=\count79
+\@clb=\count80
+\mscount=\count81
+(/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/base/tracefnt.sty
+Package: tracefnt 1997/05/29 v3.0j Standard LaTeX package (font tracing)
+\tracingfonts=\count82
+LaTeX Info: Redefining \selectfont on input line 96.
+)
+\symbold=\mathgroup4
+\symsans=\mathgroup5
+\symtypewriter=\mathgroup6
+\symitalic=\mathgroup7
+\symsmallcaps=\mathgroup8
+\symslanted=\mathgroup9
+LaTeX Font Info:    Redeclaring math alphabet \mathbf on input line 288.
+LaTeX Font Info:    Redeclaring math alphabet \mathsf on input line 289.
+LaTeX Font Info:    Redeclaring math alphabet \mathtt on input line 290.
+LaTeX Font Info:    Redeclaring math alphabet \mathit on input line 296.
+LaTeX Info: Redefining \em on input line 306.
+(/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/base/latexsym.sty
+Package: latexsym 1998/08/17 v2.2e Standard LaTeX package (lasy symbols)
+\symlasy=\mathgroup10
+LaTeX Font Info:    Overwriting symbol font `lasy' in version `bold'
+(Font)                  U/lasy/m/n --> U/lasy/b/n on input line 42.
+)
+LaTeX Font Info:    Redeclaring math delimiter \lgroup on input line 370.
+LaTeX Font Info:    Redeclaring math delimiter \rgroup on input line 372.
+LaTeX Font Info:    Redeclaring math delimiter \bracevert on input line 374.
+
+(/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/config/latex209.cf
+g
+(/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/tools/rawfonts.sty
+Compatibility mode: package `' requested, but `rawfonts' provided.
+Package: rawfonts 1994/05/08 Low-level LaTeX 2.09 font compatibility
+
+(/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/tools/somedefs.sty
+Package: somedefs 1994/06/01 Toolkit for optional definitions
+)
+LaTeX Font Info:    Try loading font information for U+lasy on input line 44.
+ (/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/base/ulasy.fd
+File: ulasy.fd 1998/08/17 v2.2eLaTeX symbol font definitions
+)))) (/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/base/article.
+cls
+Document Class: article 2000/05/19 v1.4b Standard LaTeX document class
+(/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/base/size11.clo
+File: size11.clo 2000/05/19 v1.4b Standard LaTeX file (size option)
+)
+\c@part=\count83
+\c@section=\count84
+\c@subsection=\count85
+\c@subsubsection=\count86
+\c@paragraph=\count87
+\c@subparagraph=\count88
+\c@figure=\count89
+\c@table=\count90
+\abovecaptionskip=\skip41
+\belowcaptionskip=\skip42
+Compatibility mode: definition of \rm ignored.
+Compatibility mode: definition of \sf ignored.
+Compatibility mode: definition of \tt ignored.
+Compatibility mode: definition of \bf ignored.
+Compatibility mode: definition of \it ignored.
+Compatibility mode: definition of \sl ignored.
+Compatibility mode: definition of \sc ignored.
+LaTeX Info: Redefining \cal on input line 501.
+LaTeX Info: Redefining \mit on input line 502.
+\bibindent=\dimen105
+)
+(/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/pstex/fullpage.sty
+) (doc.aux)
+\openout1 = `doc.aux'.
+
+LaTeX Font Info:    Checking defaults for OML/cmm/m/it on input line 2.
+LaTeX Font Info:    ... okay on input line 2.
+LaTeX Font Info:    Checking defaults for T1/cmr/m/n on input line 2.
+LaTeX Font Info:    ... okay on input line 2.
+LaTeX Font Info:    Checking defaults for OT1/cmr/m/n on input line 2.
+LaTeX Font Info:    ... okay on input line 2.
+LaTeX Font Info:    Checking defaults for OMS/cmsy/m/n on input line 2.
+LaTeX Font Info:    ... okay on input line 2.
+LaTeX Font Info:    Checking defaults for OMX/cmex/m/n on input line 2.
+LaTeX Font Info:    ... okay on input line 2.
+LaTeX Font Info:    Checking defaults for U/cmr/m/n on input line 2.
+LaTeX Font Info:    ... okay on input line 2.
+LaTeX Font Info:    External font `cmex10' loaded for size
+(Font)              <12> on input line 33.
+LaTeX Font Info:    External font `cmex10' loaded for size
+(Font)              <8> on input line 33.
+LaTeX Font Info:    External font `cmex10' loaded for size
+(Font)              <6> on input line 33.
+LaTeX Font Info:    Try loading font information for OMS+cmtt on input line 100
+.
+LaTeX Font Info:    No file OMScmtt.fd. on input line 100.
+LaTeX Font Warning: Font shape `OMS/cmtt/m/n' undefined
+(Font)              using `OMS/cmsy/m/n' instead
+(Font)              for symbol `textbraceleft' on input line 100.
+ [1
+
+]
+LaTeX Font Info:    External font `cmex10' loaded for size
+(Font)              <10.95> on input line 150.
+ [2] [3] [4] [5] [6]
+Overfull \hbox (1.38191pt too wide) in paragraph at lines 480--484
+[]\OT1/cmr/m/n/10.95 Emit code for \OT1/cmtt/m/n/10.95 burm[]arity\OT1/cmr/m/n/
+10.95 , \OT1/cmtt/m/n/10.95 burm[]child\OT1/cmr/m/n/10.95 , \OT1/cmtt/m/n/10.95
+ burm[]cost\OT1/cmr/m/n/10.95 , \OT1/cmtt/m/n/10.95 burm[]ntname\OT1/cmr/m/n/10
+.95 , \OT1/cmtt/m/n/10.95 burm[]op[]label\OT1/cmr/m/n/10.95 , \OT1/cmtt/m/n/10.
+95 burm[]opname\OT1/cmr/m/n/10.95 ,
+ []
+
+[7] [8] [9] (doc.aux)
+LaTeX Font Warning: Some font shapes were not available, defaults substituted.
+ ) 
+Here is how much of TeX's memory you used:
+ 543 strings out of 12968
+ 6147 string characters out of 289029
+ 446019 words of memory out of 1453895
+ 3433 multiletter control sequences out of 10000+10000
+ 23403 words of font info for 87 fonts, out of 400000 for 2000
+ 14 hyphenation exceptions out of 1000
+ 21i,6n,20p,308b,283s stack positions out of 300i,100n,500p,50000b,4000s
+
+Output written on doc.dvi (9 pages, 29856 bytes).
diff --git a/llvm/utils/Burg/Doc/doc.tex b/llvm/utils/Burg/Doc/doc.tex
new file mode 100644
index 00000000000..3dc67be3176
--- /dev/null
+++ b/llvm/utils/Burg/Doc/doc.tex
@@ -0,0 +1,596 @@
+\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}
+
diff --git a/llvm/utils/Burg/LOG_CHANGES b/llvm/utils/Burg/LOG_CHANGES
new file mode 100644
index 00000000000..804f00378b2
--- /dev/null
+++ b/llvm/utils/Burg/LOG_CHANGES
@@ -0,0 +1,10 @@
+8/20/02 -- Vikram Adve
+	be.c: Replaced "char*" with "const char*" to avoid compiler warnings.
+
+9/9/03 -- John Criswell
+	b.h be.c fe.h gram.y lex.c main.c map.c nontermainl.c plan.c zalloc.c:
+	A cursory look through our logs and comments indicates that these are
+	the only modified files.  No feature enhancements have been made;
+	rather, all changes either fix minor programming errors, get rid of
+	warnings, ANSI-ify the code, or integrate Burg into our build system.
+
diff --git a/llvm/utils/Burg/Makefile b/llvm/utils/Burg/Makefile
new file mode 100644
index 00000000000..5797161619b
--- /dev/null
+++ b/llvm/utils/Burg/Makefile
@@ -0,0 +1,28 @@
+LEVEL = ../..
+TOOLNAME = burg
+ExtraSource = gram.tab.c
+
+include $(LEVEL)/Makefile.common
+
+gram.tab.c gram.tab.h:: gram.yc
+	$(VERB) $(BISON) -o gram.tab.c -d $<
+
+$(SourceDir)/lex.c: gram.tab.h
+
+clean::
+	rm -rf gram.tab.h gram.tab.c core* *.aux *.log *.dvi sample sample.c tmp
+
+#$(BUILD_OBJ_DIR)/Release/lex.o $(BUILD_OBJ_DIR)/Profile/lex.o $(BUILD_OBJ_DIR)/Debug/lex.o: gram.tab.h
+
+doc.dvi: doc.tex
+	latex doc; latex doc
+
+
+test:: $(TOOLEXENAME_G) sample.gr
+	$(TOOLEXENAME_G) -I     <sample.gr   >sample.c && $(CC) $(CFLAGS) -o sample sample.c && ./sample
+	$(TOOLEXENAME_G) -I      sample.gr   >tmp && cmp tmp sample.c
+	$(TOOLEXENAME_G) -I     <sample.gr -o tmp && cmp tmp sample.c
+	$(TOOLEXENAME_G) -I      sample.gr -o tmp && cmp tmp sample.c
+	$(TOOLEXENAME_G) -I -O0 <sample.gr   >tmp && cmp tmp sample.c
+	$(TOOLEXENAME_G) -I -=  <sample.gr   >tmp && cmp tmp sample.c
+	$(RM) -f tmp sample.c
diff --git a/llvm/utils/Burg/README b/llvm/utils/Burg/README
new file mode 100644
index 00000000000..bc26405727e
--- /dev/null
+++ b/llvm/utils/Burg/README
@@ -0,0 +1,14 @@
+To format the documentation, type "make doc.dvi" and print the result.
+
+The length of the cost vectors is fixed at 4 for reasons that are
+primarily historical.  To change it, edit the definition of DELTAWIDTH
+in b.h.
+
+Burg is compiled without optimization by default to avoid problems
+with initial installation.  To improve burg's performance, add '-O' to
+CFLAGS in the Makefile and rebuild burg with a high quality optimizing
+compiler.
+
+To be added to the Burg mailing list, send your preferred electronic
+mail address to cwf@research.att.com.
+
diff --git a/llvm/utils/Burg/b.h b/llvm/utils/Burg/b.h
new file mode 100644
index 00000000000..164325dc976
--- /dev/null
+++ b/llvm/utils/Burg/b.h
@@ -0,0 +1,311 @@
+/* $Id$ */
+
+#define MAX_ARITY	2
+
+typedef int ItemSetNum;
+typedef int OperatorNum;
+typedef int NonTerminalNum;
+typedef int RuleNum;
+typedef int ArityNum;
+typedef int ERuleNum;
+
+extern NonTerminalNum	last_user_nonterminal;
+extern NonTerminalNum	max_nonterminal;
+extern RuleNum		max_rule;
+extern ERuleNum		max_erule_num;
+extern int		max_arity;
+
+#ifdef __STDC__
+#define ARGS(x) x
+#else
+#define ARGS(x) ()
+#endif
+
+#ifndef NOLEX
+#define DELTAWIDTH	4
+typedef short DeltaCost[DELTAWIDTH];
+typedef short *DeltaPtr;
+extern void ASSIGNCOST ARGS((DeltaPtr, DeltaPtr));
+extern void ADDCOST ARGS((DeltaPtr, DeltaPtr));
+extern void MINUSCOST ARGS((DeltaPtr, DeltaPtr));
+extern void ZEROCOST ARGS((DeltaPtr));
+extern int LESSCOST ARGS((DeltaPtr, DeltaPtr));
+extern int EQUALCOST ARGS((DeltaPtr, DeltaPtr));
+#define PRINCIPLECOST(x)	(x[0])
+#else
+#define DELTAWIDTH	1
+typedef int DeltaCost;
+typedef int DeltaPtr;
+#define ASSIGNCOST(l, r)	((l) = (r))
+#define ADDCOST(l, r)		((l) += (r))
+#define MINUSCOST(l, r)		((l) -= (r))
+#define ZEROCOST(x)		((x) = 0)
+#define LESSCOST(l, r)		((l) < (r))
+#define EQUALCOST(l, r)		((l) == (r))
+#define PRINCIPLECOST(x)	(x)
+#endif /* NOLEX */
+#define NODIVERGE(c,state,nt,base)		if (prevent_divergence > 0) CHECKDIVERGE(c,state,nt,base);
+
+struct list {
+	void		*x;
+	struct list	*next;
+};
+typedef struct list	*List;
+
+struct intlist {
+	int		x;
+	struct intlist	*next;
+};
+typedef struct intlist	*IntList;
+
+struct operator {
+	char		*name;
+	unsigned int	ref:1;
+	OperatorNum	num;
+	ItemSetNum	baseNum;
+	ItemSetNum	stateCount;
+	ArityNum	arity;
+	struct table	*table;
+};
+typedef struct operator	*Operator;
+
+struct nonterminal {
+	char		*name;
+	NonTerminalNum	num;
+	ItemSetNum	baseNum;
+	ItemSetNum	ruleCount;
+	struct plankMap *pmap;
+
+	struct rule	*sampleRule; /* diagnostic---gives "a" rule that with this lhs */
+};
+typedef struct nonterminal	*NonTerminal;
+
+struct pattern {
+	NonTerminal	normalizer;
+	Operator	op;		/* NULL if NonTerm -> NonTerm */
+	NonTerminal	children[MAX_ARITY];
+};
+typedef struct pattern	*Pattern;
+
+struct rule {
+	DeltaCost	delta;
+	ERuleNum	erulenum;
+	RuleNum		num;
+	RuleNum		newNum;
+	NonTerminal	lhs;
+	Pattern		pat;
+	unsigned int	used:1;
+};
+typedef struct rule	*Rule;
+
+struct item {
+	DeltaCost	delta;
+	Rule		rule;
+};
+typedef struct item	Item;
+
+typedef short 	*Relevant;	/* relevant non-terminals */
+
+typedef Item	*ItemArray;
+
+struct item_set {	/* indexed by NonTerminal */
+	ItemSetNum	num;
+	ItemSetNum	newNum;
+	Operator	op;
+	struct item_set *kids[2];
+	struct item_set *representative;
+	Relevant	relevant;
+	ItemArray	virgin;
+	ItemArray	closed;
+};
+typedef struct item_set	*Item_Set;
+
+#define DIM_MAP_SIZE	(1 << 8)
+#define GLOBAL_MAP_SIZE	(1 << 15)
+
+struct mapping {	/* should be a hash table for TS -> int */
+	List		*hash;
+	int		hash_size;
+	int		max_size;
+	ItemSetNum	count;
+	Item_Set	*set;	/* map: int <-> Item_Set */
+};
+typedef struct mapping	*Mapping;
+
+struct index_map {
+	ItemSetNum	max_size;
+	Item_Set	*class;
+};
+typedef struct index_map	Index_Map;
+
+struct dimension {
+	Relevant	relevant;
+	Index_Map	index_map;
+	Mapping		map;
+	ItemSetNum	max_size;
+	struct plankMap *pmap;
+};
+typedef struct dimension	*Dimension;
+
+
+struct table {
+	Operator	op;
+	List		rules;
+	Relevant	relevant;
+	Dimension	dimen[MAX_ARITY];	/* 1 for each dimension */
+	Item_Set	*transition;	/* maps local indices to global
+						itemsets */
+};
+typedef struct table	*Table;
+
+struct relation {
+	Rule	rule;
+	DeltaCost	chain;
+	NonTerminalNum	nextchain;
+	DeltaCost	sibling;
+	int		sibFlag;
+	int		sibComputed;
+};
+typedef struct relation	*Relation;
+
+struct queue {
+	List head;
+	List tail;
+};
+typedef struct queue	*Queue;
+
+struct plank {
+	char *name;
+	List fields;
+	int width;
+};
+typedef struct plank	*Plank;
+
+struct except {
+	short index;
+	short value;
+};
+typedef struct except	*Exception;
+
+struct plankMap {
+	List exceptions;
+	int offset;
+	struct stateMap *values;
+};
+typedef struct plankMap	*PlankMap;
+
+struct stateMap {
+	char *fieldname;
+	Plank plank;
+	int width;
+	short *value;
+};
+typedef struct stateMap	*StateMap;
+
+struct stateMapTable {
+	List maps;
+};
+
+extern void CHECKDIVERGE ARGS((DeltaPtr, Item_Set, int, int));
+extern void zero ARGS((Item_Set));
+extern ItemArray newItemArray ARGS((void));
+extern ItemArray itemArrayCopy ARGS((ItemArray));
+extern Item_Set newItem_Set ARGS((Relevant));
+extern void freeItem_Set ARGS((Item_Set));
+extern Mapping newMapping ARGS((int));
+extern NonTerminal newNonTerminal ARGS((char *));
+extern int nonTerminalName ARGS((char *, int));
+extern Operator newOperator ARGS((char *, OperatorNum, ArityNum));
+extern Pattern newPattern ARGS((Operator));
+extern Rule newRule ARGS((DeltaPtr, ERuleNum, NonTerminal, Pattern));
+extern List newList ARGS((void *, List));
+extern IntList newIntList ARGS((int, IntList));
+extern int length ARGS((List));
+extern List appendList ARGS((void *, List));
+extern Table newTable ARGS((Operator));
+extern Queue newQ ARGS((void));
+extern void addQ ARGS((Queue, Item_Set));
+extern Item_Set popQ ARGS((Queue));
+extern int equivSet ARGS((Item_Set, Item_Set));
+extern Item_Set decode ARGS((Mapping, ItemSetNum));
+extern Item_Set encode ARGS((Mapping, Item_Set, int *));
+extern void build ARGS((void));
+extern Item_Set *transLval ARGS((Table, int, int));
+
+typedef void *	(*ListFn) ARGS((void *));
+extern void foreachList ARGS((ListFn, List));
+extern void reveachList ARGS((ListFn, List));
+
+extern void addToTable ARGS((Table, Item_Set));
+
+extern void closure ARGS((Item_Set));
+extern void trim ARGS((Item_Set));
+extern void findChainRules ARGS((void));
+extern void findAllPairs ARGS((void));
+extern void addRelevant ARGS((Relevant, NonTerminalNum));
+
+extern void *zalloc ARGS((unsigned int));
+extern void zfree ARGS((void *));
+
+extern NonTerminal	start;
+extern List		rules;
+extern List		chainrules;
+extern List		operators;
+extern List		leaves;
+extern List		nonterminals;
+extern List		grammarNts;
+extern Queue		globalQ;
+extern Mapping		globalMap;
+extern int		exceptionTolerance;
+extern int		prevent_divergence;
+extern int		principleCost;
+extern int		lexical;
+extern struct rule	stub_rule;
+extern Relation 	*allpairs;
+extern Item_Set		*sortedStates;
+extern Item_Set		errorState;
+
+extern void dumpRelevant ARGS((Relevant));
+extern void dumpOperator ARGS((Operator, int));
+extern void dumpOperator_s ARGS((Operator));
+extern void dumpOperator_l ARGS((Operator));
+extern void dumpNonTerminal ARGS((NonTerminal));
+extern void dumpRule ARGS((Rule));
+extern void dumpRuleList ARGS((List));
+extern void dumpItem ARGS((Item *));
+extern void dumpItem_Set ARGS((Item_Set));
+extern void dumpMapping ARGS((Mapping));
+extern void dumpQ ARGS((Queue));
+extern void dumpIndex_Map ARGS((Index_Map *));
+extern void dumpDimension ARGS((Dimension));
+extern void dumpPattern ARGS((Pattern));
+extern void dumpTable ARGS((Table, int));
+extern void dumpTransition ARGS((Table));
+extern void dumpCost ARGS((DeltaCost));
+extern void dumpAllPairs ARGS((void));
+extern void dumpRelation ARGS((Relation));
+extern void dumpSortedStates ARGS((void));
+extern void dumpSortedRules ARGS((void));
+extern int debugTrim;
+
+#ifdef DEBUG
+#define debug(a,b)	if (a) b
+#else
+#define debug(a,b)
+#endif
+extern int debugTables;
+
+#define TABLE_INCR	8
+#define STATES_INCR	64
+
+#ifdef NDEBUG
+#define assert(c) ((void) 0)
+#else
+#define assert(c) ((void) ((c) || fatal(__FILE__,__LINE__)))
+#endif
+
+extern void doStart ARGS((char *));
+extern void exit ARGS((int));
+extern int fatal ARGS((const char *, int));
+extern void yyerror ARGS((const char *));
+extern void yyerror1 ARGS((const char *));
diff --git a/llvm/utils/Burg/be.c b/llvm/utils/Burg/be.c
new file mode 100644
index 00000000000..defe948d2db
--- /dev/null
+++ b/llvm/utils/Burg/be.c
@@ -0,0 +1,1052 @@
+char rcsid_be[] = "$Id$";
+
+#include <stdio.h>
+#include <string.h>
+#include "b.h"
+#include "fe.h"
+
+#define ERROR_VAL 0
+
+FILE *outfile;
+const char *prefix = "burm";
+
+static void doKids ARGS((RuleAST));
+static void doLabel ARGS((Operator));
+static void doLayout ARGS((RuleAST));
+static void doMakeTable ARGS((Operator));
+static void doVector ARGS((RuleAST));
+static void layoutNts ARGS((PatternAST));
+static void makeIndex_Map ARGS((Dimension));
+static void makePvector ARGS((void));
+static void makeState ARGS((void));
+static void printPatternAST ARGS((PatternAST));
+static void printPatternAST_int ARGS((PatternAST));
+static void setVectors ARGS((PatternAST));
+static void trailing_zeroes ARGS((int));
+static int seminal ARGS((int from, int to));
+static void printRule ARGS((RuleAST, const char *));
+
+static void
+doLabel(op) Operator op;
+{
+	fprintf(outfile, "\tcase %d:\n", op->num);
+
+	switch (op->arity) {
+	default:
+		assert(0);
+		break;
+	case 0:
+		fprintf(outfile, "\t\treturn %d;\n", op->table->transition[0]->num);
+		break;
+	case 1:
+		if (op->table->rules) {
+			fprintf(outfile, "\t\treturn %s_%s_transition[l];\n", prefix, op->name);
+		} else {
+			fprintf(outfile, "\t\treturn %d;\n", ERROR_VAL);
+		}
+		break;
+	case 2:
+		if (op->table->rules) {
+			fprintf(outfile, "\t\treturn %s_%s_transition[%s_%s_imap_1[l]][%s_%s_imap_2[r]];\n", prefix, op->name, prefix, op->name, prefix, op->name);
+		} else {
+			fprintf(outfile, "\t\treturn %d;\n", ERROR_VAL);
+		}
+		break;
+	}
+}
+
+int
+opsOfArity(arity) int arity;
+{
+	int c;
+	List l;
+
+	c = 0;
+	for (l = operators; l; l = l->next) {
+		Operator op = (Operator) l->x;
+		if (op->arity == arity) {
+			fprintf(outfile, "\tcase %d:\n", op->num);
+			c++;
+		}
+	}
+	return c;
+}
+
+static void
+trailing_zeroes(z) int z;
+{
+	int i;
+
+	for (i = 0; i < z; i++) {
+		fprintf(outfile, ", 0");
+	}
+}
+
+void
+makeLabel()
+{
+	int flag;
+
+	fprintf(outfile, "#ifdef __STDC__\n");
+	fprintf(outfile, "int %s_label(%s_NODEPTR_TYPE n) {\n", prefix, prefix);
+	fprintf(outfile, "#else\n");
+	fprintf(outfile, "int %s_label(n) %s_NODEPTR_TYPE n; {\n", prefix, prefix);
+	fprintf(outfile, "#endif\n");
+
+	fprintf(outfile, 
+	"\t%s_assert(n, %s_PANIC(\"NULL pointer passed to %s_label\\n\"));\n",
+				prefix, prefix, prefix);
+	fprintf(outfile, "\tswitch (%s_OP_LABEL(n)) {\n", prefix);
+	fprintf(outfile, "\tdefault: %s_PANIC(\"Bad op %%d in %s_label\\n\", %s_OP_LABEL(n)); abort(); return 0;\n", 
+			prefix, prefix, prefix);
+
+	flag = opsOfArity(0);
+	if (flag > 0) {
+		fprintf(outfile, "\t\treturn %s_STATE_LABEL(n) = %s_state(%s_OP_LABEL(n)",
+					prefix, prefix, prefix);
+		trailing_zeroes(max_arity);
+		fprintf(outfile, ");\n");
+	}
+	flag = opsOfArity(1);
+	if (flag > 0) {
+		fprintf(outfile, "\t\treturn %s_STATE_LABEL(n) = %s_state(%s_OP_LABEL(n), %s_label(%s_LEFT_CHILD(n))",
+					prefix, prefix, prefix, prefix, prefix);
+		trailing_zeroes(max_arity-1);
+		fprintf(outfile, ");\n");
+	}
+	flag = opsOfArity(2);
+	if (flag > 0) {
+		fprintf(outfile, "\t\treturn %s_STATE_LABEL(n) = %s_state(%s_OP_LABEL(n), %s_label(%s_LEFT_CHILD(n)), %s_label(%s_RIGHT_CHILD(n))",
+					prefix, prefix, prefix, prefix, prefix, prefix, prefix);
+		trailing_zeroes(max_arity-2);
+		fprintf(outfile, ");\n");
+
+	}
+	fprintf(outfile, "\t}\n");
+	fprintf(outfile, "}\n");
+}
+
+static void
+makeState()
+{
+	fprintf(outfile, "int %s_state(int op, int l, int r) {\n", prefix);
+	fprintf(outfile, 
+	"\t%s_assert(l >= 0 && l < %d, PANIC(\"Bad state %%d passed to %s_state\\n\", l));\n",
+				prefix, globalMap->count, prefix);
+	fprintf(outfile, 
+	"\t%s_assert(r >= 0 && r < %d, PANIC(\"Bad state %%d passed to %s_state\\n\", r));\n",
+				prefix, globalMap->count, prefix);
+	fprintf(outfile, "\tswitch (op) {\n");
+	fprintf(outfile, "\tdefault: %s_PANIC(\"Bad op %%d in %s_state\\n\", op); abort(); return 0;\n", prefix, prefix);
+
+	foreachList((ListFn) doLabel, operators);
+
+	fprintf(outfile, "\t}\n");
+	fprintf(outfile, "}\n");
+}
+
+static char cumBuf[4000];
+static int vecIndex;
+char vecBuf[4000];
+
+static void
+setVectors(ast) PatternAST ast;
+{
+	char old[4000];
+
+	switch (ast->sym->tag) {
+	default:
+		assert(0);
+		break;
+	case NONTERMINAL:
+		sprintf(old, "\t\tkids[%d] = %s;\n", vecIndex, vecBuf);
+		strcat(cumBuf, old);
+		vecIndex++;
+		return;
+	case OPERATOR:
+		switch (ast->sym->u.op->arity) {
+		default:
+			assert(0);
+			break;
+		case 0:
+			return;
+		case 1:
+			strcpy(old, vecBuf);
+			sprintf(vecBuf, "%s_LEFT_CHILD(%s)", prefix, old);
+			setVectors((PatternAST) ast->children->x);
+			strcpy(vecBuf, old);
+			return;
+		case 2:
+			strcpy(old, vecBuf);
+			sprintf(vecBuf, "%s_LEFT_CHILD(%s)", prefix, old);
+			setVectors((PatternAST) ast->children->x);
+
+			sprintf(vecBuf, "%s_RIGHT_CHILD(%s)", prefix, old);
+			setVectors((PatternAST) ast->children->next->x);
+			strcpy(vecBuf, old);
+			return;
+		}
+		break;
+	}
+}
+
+#define MAX_VECTOR	10
+
+void
+makeRuleTable()
+{
+	int s,nt;
+
+	fprintf(outfile, "static short %s_RuleNo[%d][%d] = {\n", prefix, globalMap->count, last_user_nonterminal-1);
+	for (s = 0; s < globalMap->count; s++) {
+		Item_Set ts = globalMap->set[s];
+		if (s > 0) {
+			fprintf(outfile, ",\n");
+		}
+		fprintf(outfile, "/* state %d */\n", s);
+		fprintf(outfile, "{");
+		for (nt = 1; nt < last_user_nonterminal; nt++) {
+			if (nt > 1) {
+				fprintf(outfile, ",");
+				if (nt % 10 == 1) {
+					fprintf(outfile, "\t/* state %d; Nonterminals %d-%d */\n", s, nt-10, nt-1);
+				}
+			}
+			if (ts->closed[nt].rule) {
+				ts->closed[nt].rule->used = 1;
+				fprintf(outfile, "%5d", ts->closed[nt].rule->erulenum);
+			} else {
+				fprintf(outfile, "%5d", ERROR_VAL);
+			}
+		}
+		fprintf(outfile, "}");
+	}
+	fprintf(outfile, "};\n");
+}
+
+static void
+makeIndex_Map(d) Dimension d;
+{
+	int s;
+
+	for (s = 0; s < globalMap->count; s++) {
+		if (s > 0) {
+			fprintf(outfile, ",");
+			if (s % 10 == 0) {
+				fprintf(outfile, "\t/* %d-%d */\n", s-10, s-1);
+			}
+		}
+		fprintf(outfile, "%5d", d->map->set[d->index_map.class[s]->num]->num);
+	}
+	fprintf(outfile, "};\n");
+}
+
+static void
+doMakeTable(op) Operator op;
+{
+	int s;
+	int i,j;
+	Dimension d;
+
+	switch (op->arity) {
+	default:
+		assert(0);
+		break;
+	case 0:
+		return;
+	case 1:
+		if (!op->table->rules) {
+			return;
+		}
+		d = op->table->dimen[0];
+		fprintf(outfile, "static short %s_%s_transition[%d] = {\n", prefix, op->name, globalMap->count);
+		for (s = 0; s < globalMap->count; s++) {
+			if (s > 0) {
+				fprintf(outfile, ", ");
+				if (s % 10 == 0) {
+					fprintf(outfile, "\t/* %d-%d */\n", s-10, s-1);
+				}
+			}
+			fprintf(outfile, "%5d", op->table->transition[d->map->set[d->index_map.class[s]->num]->num]->num);
+		}
+		fprintf(outfile, "};\n");
+		break;
+	case 2:
+		if (!op->table->rules) {
+			return;
+		}
+		fprintf(outfile, "static short %s_%s_imap_1[%d] = {\n", prefix, op->name, globalMap->count);
+		makeIndex_Map(op->table->dimen[0]);
+		fprintf(outfile, "static short %s_%s_imap_2[%d] = {\n", prefix, op->name, globalMap->count);
+		makeIndex_Map(op->table->dimen[1]);
+
+		fprintf(outfile, "static short %s_%s_transition[%d][%d] = {", prefix, op->name,
+						op->table->dimen[0]->map->count,
+						op->table->dimen[1]->map->count);
+		for (i = 0; i < op->table->dimen[0]->map->count; i++) {
+			if (i > 0) {
+				fprintf(outfile, ",");
+			}
+			fprintf(outfile, "\n");
+			fprintf(outfile, "{");
+			for (j = 0; j < op->table->dimen[1]->map->count; j++) {
+				Item_Set *ts = transLval(op->table, i, j);
+				if (j > 0) {
+					fprintf(outfile, ",");
+				}
+				fprintf(outfile, "%5d", (*ts)->num);
+			}
+			fprintf(outfile, "}\t/* row %d */", i);
+		}
+		fprintf(outfile, "\n};\n");
+
+		break;
+	}
+}
+
+void
+makeTables()
+{
+	foreachList((ListFn) doMakeTable, operators);
+}
+
+RuleAST *pVector;
+
+void
+makeLHSmap()
+{
+	int i;
+
+	if (!pVector) {
+		makePvector();
+	}
+
+	fprintf(outfile, "short %s_lhs[] = {\n", prefix);
+	for (i = 0; i <= max_erule_num; i++) {
+		if (pVector[i]) {
+			fprintf(outfile, "\t%s_%s_NT,\n", prefix, pVector[i]->lhs);
+		} else {
+			fprintf(outfile, "\t0,\n");
+		}
+	}
+	fprintf(outfile, "};\n\n");
+}
+
+static int seminal(int from, int to)
+{
+	return allpairs[from][to].rule ? allpairs[from][to].rule->erulenum : 0;
+
+	/*
+	int tmp, last;
+	tmp = 0;
+	for (;;) {
+		last = tmp;
+		tmp = allpairs[to][from].rule ? allpairs[to][from].rule->erulenum : 0;
+		if (!tmp) {
+			break;
+		}
+		assert(pVector[tmp]);
+		to = pVector[tmp]->rule->pat->children[0]->num;
+	}
+	return last;
+	*/
+}
+
+void
+makeClosureArray()
+{
+	int i, j;
+
+	if (!pVector) {
+		makePvector();
+	}
+
+	fprintf(outfile, "short %s_closure[%d][%d] = {\n", prefix, last_user_nonterminal, last_user_nonterminal);
+	for (i = 0; i < last_user_nonterminal; i++) {
+		fprintf(outfile, "\t{");
+		for (j = 0; j < last_user_nonterminal; j++) {
+			if (j > 0 && j%10 == 0) {
+				fprintf(outfile, "\n\t ");
+			}
+			fprintf(outfile, " %4d,", seminal(i,j));
+		}
+		fprintf(outfile, "},\n");
+	}
+	fprintf(outfile, "};\n");
+}
+
+void
+makeCostVector(z,d) int z; DeltaCost d;
+{
+	fprintf(outfile, "\t{");
+#ifdef NOLEX
+	if (z) {
+		fprintf(outfile, "%5d", d);
+	} else {
+		fprintf(outfile, "%5d", 0);
+	}
+#else
+	{
+	int j;
+	for (j = 0; j < DELTAWIDTH; j++) {
+		if (j > 0) {
+			fprintf(outfile, ",");
+		}
+		if (z) {
+			fprintf(outfile, "%5d", d[j]);
+		} else {
+			fprintf(outfile, "%5d", 0);
+		}
+	}
+	}
+#endif /* NOLEX */
+	fprintf(outfile, "}");
+}
+
+void
+makeCostArray()
+{
+	int i;
+
+	if (!pVector) {
+		makePvector();
+	}
+
+	fprintf(outfile, "short %s_cost[][%d] = {\n", prefix, DELTAWIDTH);
+	for (i = 0; i <= max_erule_num; i++) {
+		makeCostVector(pVector[i], pVector[i] ? pVector[i]->rule->delta : 0);
+		fprintf(outfile, ", /* ");
+		printRule(pVector[i], "(none)");
+		fprintf(outfile, " = %d */\n", i);
+	}
+	fprintf(outfile, "};\n");
+}
+
+void
+makeStateStringArray()
+{
+	int s;
+	int nt;
+	int states;
+	
+	states = globalMap->count;
+	fprintf(outfile, "\nconst char * %s_state_string[] = {\n", prefix);
+	fprintf(outfile, "\" not a state\", /* state 0 */\n");
+	for (s = 0; s < states-1; s++) {
+		fprintf(outfile, "\t\"");
+		printRepresentative(outfile, sortedStates[s]);
+		fprintf(outfile, "\", /* state #%d */\n", s+1);
+	}
+	fprintf(outfile, "};\n");
+}
+
+void
+makeDeltaCostArray()
+{
+	int s;
+	int nt;
+	int states;
+	
+	states = globalMap->count;
+	fprintf(outfile, "\nshort %s_delta_cost[%d][%d][%d] = {\n", prefix, states, last_user_nonterminal, DELTAWIDTH);
+	fprintf(outfile, "{{0}}, /* state 0 */\n");
+	for (s = 0; s < states-1; s++) {
+		fprintf(outfile, "{ /* state #%d: ", s+1);
+		printRepresentative(outfile, sortedStates[s]);
+		fprintf(outfile, " */\n");
+		fprintf(outfile, "\t{0},\n");
+		for (nt = 1; nt < last_user_nonterminal; nt++) {
+			makeCostVector(1, sortedStates[s]->closed[nt].delta);
+			fprintf(outfile, ", /* ");
+			if (sortedStates[s]->closed[nt].rule) {
+				int erulenum = sortedStates[s]->closed[nt].rule->erulenum;
+				printRule(pVector[erulenum], "(none)");
+				fprintf(outfile, " = %d */", erulenum);
+			} else {
+				fprintf(outfile, "(none) */");
+			}
+			fprintf(outfile, "\n");
+		}
+		fprintf(outfile, "},\n");
+	}
+	fprintf(outfile, "};\n");
+}
+
+static void
+printPatternAST_int(p) PatternAST p;
+{
+	List l;
+
+	if (p) {
+		switch (p->sym->tag) {
+		case NONTERMINAL:
+			fprintf(outfile, "%5d,", -p->sym->u.nt->num);
+			break;
+		case OPERATOR:
+			fprintf(outfile, "%5d,", p->sym->u.op->num);
+			break;
+		default:
+			assert(0);
+		}
+		if (p->children) {
+			for (l = p->children; l; l = l->next) {
+				PatternAST pat = (PatternAST) l->x;
+				printPatternAST_int(pat);
+			}
+		}
+	}
+}
+
+static void
+printPatternAST(p) PatternAST p;
+{
+	List l;
+
+	if (p) {
+		fprintf(outfile, "%s", p->op);
+		if (p->children) {
+			fprintf(outfile, "(");
+			for (l = p->children; l; l = l->next) {
+				PatternAST pat = (PatternAST) l->x;
+				if (l != p->children) {
+					fprintf(outfile, ", ");
+				}
+				printPatternAST(pat);
+			}
+			fprintf(outfile, ")");
+		}
+	}
+}
+
+static void
+layoutNts(ast) PatternAST ast;
+{
+	char out[30];
+
+	switch (ast->sym->tag) {
+	default:
+		assert(0);
+		break;
+	case NONTERMINAL:
+		sprintf(out, "%d, ", ast->sym->u.nt->num);
+		strcat(cumBuf, out);
+		return;
+	case OPERATOR:
+		switch (ast->sym->u.op->arity) {
+		default:
+			assert(0);
+			break;
+		case 0:
+			return;
+		case 1:
+			layoutNts((PatternAST) ast->children->x);
+			return;
+		case 2:
+			layoutNts((PatternAST) ast->children->x);
+			layoutNts((PatternAST) ast->children->next->x);
+			return;
+		}
+		break;
+	}
+}
+
+static void
+doVector(ast) RuleAST ast;
+{
+	if (pVector[ast->rule->erulenum]) {
+		fprintf(stderr, "ERROR: non-unique external rule number: (%d)\n", ast->rule->erulenum);
+		exit(1);
+	}
+	pVector[ast->rule->erulenum] = ast;
+}
+
+static void
+makePvector()
+{
+	pVector = (RuleAST*) zalloc((max_erule_num+1) * sizeof(RuleAST));
+	foreachList((ListFn) doVector, ruleASTs);
+}
+
+static void
+doLayout(ast) RuleAST ast;
+{
+	sprintf(cumBuf, "{ ");
+	layoutNts(ast->pat);
+	strcat(cumBuf, "0 }");
+}
+
+void
+makeNts()
+{
+	int i;
+	int new;
+	StrTable nts;
+
+	nts = newStrTable();
+
+	if (!pVector) {
+		makePvector();
+	}
+
+	for (i = 0; i <= max_erule_num; i++) {
+		if (pVector[i]) {
+			doLayout(pVector[i]);
+			pVector[i]->nts = addString(nts, cumBuf, i, &new);
+			if (new) {
+				char ename[50];
+
+				sprintf(ename, "%s_r%d_nts", prefix, i);
+				pVector[i]->nts->ename = (char*) zalloc(strlen(ename)+1);
+				strcpy(pVector[i]->nts->ename, ename);
+				fprintf(outfile, "static short %s[] =", ename);
+				fprintf(outfile, "%s;\n", cumBuf);
+			}
+		}
+	}
+
+	fprintf(outfile, "short *%s_nts[] = {\n", prefix);
+	for (i = 0; i <= max_erule_num; i++) {
+		if (pVector[i]) {
+			fprintf(outfile, "\t%s,\n", pVector[i]->nts->ename);
+		} else {
+			fprintf(outfile, "\t0,\n");
+		}
+	}
+	fprintf(outfile, "};\n");
+}
+
+static void
+printRule(RuleAST r, const char *d)
+{
+	if (r) {
+		fprintf(outfile, "%s: ", r->rule->lhs->name);
+		printPatternAST(r->pat);
+	} else {
+		fprintf(outfile, "%s", d);
+	}
+}
+
+void
+makeRuleDescArray()
+{
+	int i;
+
+	if (!pVector) {
+		makePvector();
+	}
+
+	if (last_user_nonterminal != max_nonterminal) {
+		/* not normal form */
+		fprintf(outfile, "short %s_rule_descriptor_0[] = { 0, 0 };\n", prefix);
+	} else {
+		fprintf(outfile, "short %s_rule_descriptor_0[] = { 0, 1 };\n", prefix);
+	}
+	for (i = 1; i <= max_erule_num; i++) {
+		if (pVector[i]) {
+			Operator o;
+			NonTerminal t;
+
+			fprintf(outfile, "short %s_rule_descriptor_%d[] = {", prefix, i);
+			fprintf(outfile, "%5d,", -pVector[i]->rule->lhs->num);
+			printPatternAST_int(pVector[i]->pat);
+			fprintf(outfile, " };\n");
+		}
+	}
+
+	fprintf(outfile, "/* %s_rule_descriptors[0][1] = 1 iff grammar is normal form. */\n", prefix);
+	fprintf(outfile, "short * %s_rule_descriptors[] = {\n", prefix);
+	fprintf(outfile, "\t%s_rule_descriptor_0,\n", prefix);
+	for (i = 1; i <= max_erule_num; i++) {
+		if (pVector[i]) {
+			fprintf(outfile, "\t%s_rule_descriptor_%d,\n", prefix, i);
+		} else {
+			fprintf(outfile, "\t%s_rule_descriptor_0,\n", prefix);
+		}
+	}
+	fprintf(outfile, "};\n");
+}
+
+
+void
+makeRuleDescArray2()
+{
+	int i;
+
+	if (!pVector) {
+		makePvector();
+	}
+
+	fprintf(outfile, "struct { int lhs, op, left, right; } %s_rule_struct[] = {\n", prefix);
+	if (last_user_nonterminal != max_nonterminal) {
+		/* not normal form */
+		fprintf(outfile, "\t{-1},");
+	} else {
+		fprintf(outfile, "\t{0},");
+	}
+	fprintf(outfile, " /* 0 if normal form, -1 if not normal form */\n");
+	for (i = 1; i <= max_erule_num; i++) {
+		fprintf(outfile, "\t");
+		if (pVector[i]) {
+			Operator o;
+			NonTerminal t1, t2;
+
+			fprintf(outfile, "{");
+			fprintf(outfile, "%5d, %5d, %5d, %5d",
+				pVector[i]->rule->lhs->num,
+				(o = pVector[i]->rule->pat->op) ? o->num : 0,
+				(t1 = pVector[i]->rule->pat->children[0]) ? t1->num : 0,
+				(t2 = pVector[i]->rule->pat->children[1]) ? t2->num : 0
+				);
+			fprintf(outfile, "} /* ");
+			printRule(pVector[i], "0");
+			fprintf(outfile, " = %d */", i);
+		} else {
+			fprintf(outfile, "{0}");
+		}
+		fprintf(outfile, ",\n");
+	}
+	fprintf(outfile, "};\n");
+}
+
+void
+makeStringArray()
+{
+	int i;
+
+	if (!pVector) {
+		makePvector();
+	}
+
+	fprintf(outfile, "const char *%s_string[] = {\n", prefix);
+	for (i = 0; i <= max_erule_num; i++) {
+		fprintf(outfile, "\t");
+		if (pVector[i]) {
+			fprintf(outfile, "\"");
+			printRule(pVector[i], "0");
+			fprintf(outfile, "\"");
+		} else {
+			fprintf(outfile, "0");
+		}
+		fprintf(outfile, ",\n");
+	}
+	fprintf(outfile, "};\n");
+	fprintf(outfile, "int %s_max_rule = %d;\n", prefix, max_erule_num);
+	fprintf(outfile, "#define %s_Max_rule %d\n", prefix, max_erule_num);
+}
+
+void
+makeRule()
+{
+	fprintf(outfile, "int %s_rule(int state, int goalnt) {\n", prefix);
+	fprintf(outfile, 
+	"\t%s_assert(state >= 0 && state < %d, PANIC(\"Bad state %%d passed to %s_rule\\n\", state));\n",
+				prefix, globalMap->count, prefix);
+	fprintf(outfile, 
+	"\t%s_assert(goalnt >= 1 && goalnt < %d, PANIC(\"Bad goalnt %%d passed to %s_rule\\n\", state));\n",
+				prefix, max_nonterminal, prefix);
+	fprintf(outfile, "\treturn %s_RuleNo[state][goalnt-1];\n", prefix);
+	fprintf(outfile, "};\n");
+}
+
+static StrTable kids;
+
+static void
+doKids(ast) RuleAST ast;
+{
+	int new;
+
+	vecIndex = 0;
+	cumBuf[0] = 0;
+	strcpy(vecBuf, "p");
+	setVectors(ast->pat);
+
+	ast->kids = addString(kids, cumBuf, ast->rule->erulenum, &new);
+
+}
+
+void
+makeKids()
+{
+	List e;
+	IntList r;
+
+	kids = newStrTable();
+
+	fprintf(outfile, "#ifdef __STDC__\n");
+	fprintf(outfile, "%s_NODEPTR_TYPE * %s_kids(%s_NODEPTR_TYPE p, int rulenumber, %s_NODEPTR_TYPE *kids) {\n", prefix, prefix, prefix, prefix);
+	fprintf(outfile, "#else\n");
+	fprintf(outfile, "%s_NODEPTR_TYPE * %s_kids(p, rulenumber, kids) %s_NODEPTR_TYPE p; int rulenumber; %s_NODEPTR_TYPE *kids; {\n", prefix, prefix, prefix, prefix);
+	fprintf(outfile, "#endif\n");
+
+	fprintf(outfile, 
+	"\t%s_assert(p, %s_PANIC(\"NULL node pointer passed to %s_kids\\n\"));\n",
+				prefix, prefix, prefix);
+	fprintf(outfile, 
+	"\t%s_assert(kids, %s_PANIC(\"NULL kids pointer passed to %s_kids\\n\"));\n",
+				prefix, prefix, prefix);
+	fprintf(outfile, "\tswitch (rulenumber) {\n");
+	fprintf(outfile, "\tdefault:\n");
+	fprintf(outfile, "\t\t%s_PANIC(\"Unknown Rule %%d in %s_kids;\\n\", rulenumber);\n", prefix, prefix);
+	fprintf(outfile, "\t\tabort();\n");
+	fprintf(outfile, "\t\t/* NOTREACHED */\n");
+
+	foreachList((ListFn) doKids, ruleASTs);
+
+	for (e = kids->elems; e; e = e->next) {
+		StrTableElement el = (StrTableElement) e->x;
+		for (r = el->erulenos; r; r = r->next) {
+			int i = r->x;
+			fprintf(outfile, "\tcase %d:\n", i);
+		}
+		fprintf(outfile, "%s", el->str);
+		fprintf(outfile, "\t\tbreak;\n");
+	}
+	fprintf(outfile, "\t}\n");
+	fprintf(outfile, "\treturn kids;\n");
+	fprintf(outfile, "}\n");
+}
+
+void
+makeOpLabel()
+{
+	fprintf(outfile, "#ifdef __STDC__\n");
+	fprintf(outfile, "int %s_op_label(%s_NODEPTR_TYPE p) {\n", prefix, prefix);
+	fprintf(outfile, "#else\n");
+	fprintf(outfile, "int %s_op_label(p) %s_NODEPTR_TYPE p; {\n", prefix, prefix);
+	fprintf(outfile, "#endif\n");
+	fprintf(outfile, 
+	"\t%s_assert(p, %s_PANIC(\"NULL pointer passed to %s_op_label\\n\"));\n",
+				prefix, prefix, prefix);
+	fprintf(outfile, "\treturn %s_OP_LABEL(p);\n", prefix);
+	fprintf(outfile, "}\n");
+}
+
+void
+makeStateLabel()
+{
+	fprintf(outfile, "#ifdef __STDC__\n");
+	fprintf(outfile, "int %s_state_label(%s_NODEPTR_TYPE p) {\n", prefix, prefix);
+	fprintf(outfile, "#else\n");
+	fprintf(outfile, "int %s_state_label(p) %s_NODEPTR_TYPE p; {\n", prefix, prefix);
+	fprintf(outfile, "#endif\n");
+
+	fprintf(outfile, 
+	"\t%s_assert(p, %s_PANIC(\"NULL pointer passed to %s_state_label\\n\"));\n",
+				prefix, prefix, prefix);
+	fprintf(outfile, "\treturn %s_STATE_LABEL(p);\n", prefix);
+	fprintf(outfile, "}\n");
+}
+
+void
+makeChild()
+{
+	fprintf(outfile, "#ifdef __STDC__\n");
+	fprintf(outfile, "%s_NODEPTR_TYPE %s_child(%s_NODEPTR_TYPE p, int index) {\n", prefix, prefix, prefix);
+	fprintf(outfile, "#else\n");
+	fprintf(outfile, "%s_NODEPTR_TYPE %s_child(p, index) %s_NODEPTR_TYPE p; int index; {\n", prefix, prefix, prefix);
+	fprintf(outfile, "#endif\n");
+
+	fprintf(outfile, 
+	"\t%s_assert(p, %s_PANIC(\"NULL pointer passed to %s_child\\n\"));\n",
+				prefix, prefix, prefix);
+	fprintf(outfile, "\tswitch (index) {\n");
+	fprintf(outfile, "\tcase 0:\n");
+	fprintf(outfile, "\t\treturn %s_LEFT_CHILD(p);\n", prefix);
+	fprintf(outfile, "\tcase 1:\n");
+	fprintf(outfile, "\t\treturn %s_RIGHT_CHILD(p);\n", prefix);
+	fprintf(outfile, "\t}\n");
+	fprintf(outfile, "\t%s_PANIC(\"Bad index %%d in %s_child;\\n\", index);\n", prefix, prefix);
+	fprintf(outfile, "\tabort();\n");
+	fprintf(outfile, "\treturn 0;\n");
+	fprintf(outfile, "}\n");
+}
+
+static Operator *opVector;
+static int maxOperator;
+
+void
+makeOperatorVector()
+{
+	List l;
+
+	maxOperator = 0;
+	for (l = operators; l; l = l->next) {
+		Operator op = (Operator) l->x;
+		if (op->num > maxOperator) {
+			maxOperator = op->num;
+		}
+	}
+	opVector = (Operator*) zalloc((maxOperator+1) * sizeof(*opVector));
+	for (l = operators; l; l = l->next) {
+		Operator op = (Operator) l->x;
+		if (opVector[op->num]) {
+			fprintf(stderr, "ERROR: Non-unique external symbol number (%d)\n", op->num);
+			exit(1);
+		}
+		opVector[op->num] = op;
+	}
+}
+
+void
+makeOperators()
+{
+	int i;
+
+	if (!opVector) {
+		makeOperatorVector();
+	}
+	fprintf(outfile, "const char * %s_opname[] = {\n", prefix);
+	for (i = 0; i <= maxOperator; i++) {
+		if (i > 0) {
+			fprintf(outfile, ", /* %d */\n", i-1);
+		}
+		if (opVector[i]) {
+			fprintf(outfile, "\t\"%s\"", opVector[i]->name);
+		} else {
+			fprintf(outfile, "\t0");
+		}
+	}
+	fprintf(outfile, "\n};\n");
+	fprintf(outfile, "char %s_arity[] = {\n", prefix);
+	for (i = 0; i <= maxOperator; i++) {
+		if (i > 0) {
+			fprintf(outfile, ", /* %d */\n", i-1);
+		}
+		fprintf(outfile, "\t%d", opVector[i] ? opVector[i]->arity : -1);
+	}
+	fprintf(outfile, "\n};\n");
+	fprintf(outfile, "int %s_max_op = %d;\n", prefix, maxOperator);
+	fprintf(outfile, "int %s_max_state = %d;\n", prefix, globalMap->count-1);
+	fprintf(outfile, "#define %s_Max_state %d\n", prefix, globalMap->count-1);
+}
+
+void
+makeDebug()
+{
+	fprintf(outfile, "#ifdef DEBUG\n");
+	fprintf(outfile, "int %s_debug;\n", prefix);
+	fprintf(outfile, "#endif /* DEBUG */\n");
+}
+
+void
+makeSimple()
+{
+	makeRuleTable();
+	makeTables();
+	makeRule();
+	makeState();
+}
+
+void
+startOptional()
+{
+	fprintf(outfile, "#ifdef %s_STATE_LABEL\n", prefix);
+	fprintf(outfile, "#define %s_INCLUDE_EXTRA\n", prefix);
+	fprintf(outfile, "#else\n");
+	fprintf(outfile, "#ifdef STATE_LABEL\n");
+	fprintf(outfile, "#define %s_INCLUDE_EXTRA\n", prefix);
+	fprintf(outfile, "#define %s_STATE_LABEL \tSTATE_LABEL\n", prefix);
+	fprintf(outfile, "#define %s_NODEPTR_TYPE\tNODEPTR_TYPE\n", prefix);
+	fprintf(outfile, "#define %s_LEFT_CHILD  \tLEFT_CHILD\n", prefix);
+	fprintf(outfile, "#define %s_OP_LABEL    \tOP_LABEL\n", prefix);
+	fprintf(outfile, "#define %s_RIGHT_CHILD \tRIGHT_CHILD\n", prefix);
+	fprintf(outfile, "#endif /* STATE_LABEL */\n");
+	fprintf(outfile, "#endif /* %s_STATE_LABEL */\n\n", prefix);
+
+	fprintf(outfile, "#ifdef %s_INCLUDE_EXTRA\n\n", prefix);
+
+}
+
+void
+makeNonterminals()
+{
+	List l;
+
+	for (l = nonterminals; l; l = l->next) {
+		NonTerminal nt = (NonTerminal) l->x;
+		if (nt->num < last_user_nonterminal) {
+			fprintf(outfile, "#define %s_%s_NT %d\n", prefix, nt->name, nt->num);
+		}
+	}
+	fprintf(outfile, "#define %s_NT %d\n", prefix, last_user_nonterminal-1);
+}
+
+void
+makeNonterminalArray()
+{
+	int i;
+	List l;
+	NonTerminal *nta;
+
+	nta = (NonTerminal *) zalloc(sizeof(*nta) * last_user_nonterminal);
+
+	for (l = nonterminals; l; l = l->next) {
+		NonTerminal nt = (NonTerminal) l->x;
+		if (nt->num < last_user_nonterminal) {
+			nta[nt->num] = nt;
+		}
+	}
+
+	fprintf(outfile, "const char *%s_ntname[] = {\n", prefix);
+	fprintf(outfile, "\t\"Error: Nonterminals are > 0\",\n");
+	for (i = 1; i < last_user_nonterminal; i++) {
+		fprintf(outfile, "\t\"%s\",\n", nta[i]->name);
+	}
+	fprintf(outfile, "\t0\n");
+	fprintf(outfile, "};\n\n");
+
+	zfree(nta);
+}
+
+void
+endOptional()
+{
+	fprintf(outfile, "#endif /* %s_INCLUDE_EXTRA */\n", prefix);
+}
+
+void
+startBurm()
+{
+	fprintf(outfile, "#ifndef %s_PANIC\n", prefix);
+	fprintf(outfile, "#define %s_PANIC\tPANIC\n", prefix);
+	fprintf(outfile, "#endif /* %s_PANIC */\n", prefix);
+	fprintf(outfile, "#ifdef __STDC__\n");
+	fprintf(outfile, "extern void abort(void);\n");
+	fprintf(outfile, "#else\n");
+	fprintf(outfile, "extern void abort();\n");
+	fprintf(outfile, "#endif\n");
+	fprintf(outfile, "#ifdef NDEBUG\n");
+ 	fprintf(outfile, "#define %s_assert(x,y)\t;\n", prefix);
+	fprintf(outfile, "#else\n");
+ 	fprintf(outfile, "#define %s_assert(x,y)\tif(!(x)) {y; abort();}\n", prefix);
+	fprintf(outfile, "#endif\n");
+}
+
+void
+reportDiagnostics()
+{
+	List l;
+
+	for (l = operators; l; l = l->next) {
+		Operator op = (Operator) l->x;
+		if (!op->ref) {
+			fprintf(stderr, "warning: Unreferenced Operator: %s\n", op->name);
+		}
+	}
+	for (l = rules; l; l = l->next) {
+		Rule r = (Rule) l->x;
+		if (!r->used && r->num < max_ruleAST) {
+			fprintf(stderr, "warning: Unused Rule: #%d\n", r->erulenum);
+		}
+	}
+	if (!start->pmap) {
+		fprintf(stderr, "warning: Start Nonterminal (%s) does not appear on LHS.\n", start->name);
+	}
+
+	fprintf(stderr, "start symbol = \"%s\"\n", start->name);
+	fprintf(stderr, "# of states = %d\n", globalMap->count-1);
+	fprintf(stderr, "# of nonterminals = %d\n", max_nonterminal-1);
+	fprintf(stderr, "# of user nonterminals = %d\n", last_user_nonterminal-1);
+	fprintf(stderr, "# of rules = %d\n", max_rule);
+	fprintf(stderr, "# of user rules = %d\n", max_ruleAST);
+}
diff --git a/llvm/utils/Burg/burg.shar.gz b/llvm/utils/Burg/burg.shar.gz
new file mode 100644
index 00000000000..173bbfde9f6
--- /dev/null
+++ b/llvm/utils/Burg/burg.shar.gz
diff --git a/llvm/utils/Burg/burs.c b/llvm/utils/Burg/burs.c
new file mode 100644
index 00000000000..b4f8b83d00e
--- /dev/null
+++ b/llvm/utils/Burg/burs.c
@@ -0,0 +1,71 @@
+char rcsid_burs[] = "$Id$";
+
+#include "b.h"
+
+Item_Set errorState;
+
+static void doLeaf ARGS((Operator));
+
+static void
+doLeaf(leaf) Operator leaf;
+{
+	int new;
+	List pl;
+	Item_Set ts;
+	Item_Set tmp;
+
+	assert(leaf->arity == 0);
+
+	ts = newItem_Set(leaf->table->relevant);
+
+	for (pl = rules; pl; pl = pl->next) {
+		Rule p = (Rule) pl->x;
+		if (p->pat->op == leaf) {	
+			if (!ts->virgin[p->lhs->num].rule || p->delta < ts->virgin[p->lhs->num].delta) {
+				ts->virgin[p->lhs->num].rule = p;
+				ASSIGNCOST(ts->virgin[p->lhs->num].delta, p->delta);
+				ts->op = leaf;
+			}
+		}
+	}
+	trim(ts);
+	zero(ts);
+	tmp = encode(globalMap, ts, &new);
+	if (new) {
+		closure(ts);
+		leaf->table->transition[0] = ts;
+		addQ(globalQ, ts);
+	} else {
+		leaf->table->transition[0] = tmp;
+		freeItem_Set(ts);
+	}
+}
+
+void
+build()
+{
+	int new;
+	List ol;
+	Item_Set ts;
+
+	globalQ = newQ();
+	globalMap = newMapping(GLOBAL_MAP_SIZE);
+
+	ts = newItem_Set(0);
+	errorState = encode(globalMap, ts, &new);
+	ts->closed = ts->virgin;
+	addQ(globalQ, ts);
+
+	foreachList((ListFn) doLeaf, leaves);
+
+	debug(debugTables, printf("---initial set of states ---\n"));
+	debug(debugTables, dumpMapping(globalMap));
+	debug(debugTables, foreachList((ListFn) dumpItem_Set, globalQ->head));
+	
+	for (ts = popQ(globalQ); ts; ts = popQ(globalQ)) {
+		for (ol = operators; ol; ol = ol->next) {
+			Operator op = (Operator) ol->x;
+			addToTable(op->table, ts);
+		}
+	}
+}
diff --git a/llvm/utils/Burg/closure.c b/llvm/utils/Burg/closure.c
new file mode 100644
index 00000000000..70e16264ebb
--- /dev/null
+++ b/llvm/utils/Burg/closure.c
@@ -0,0 +1,95 @@
+char rcsid_closure[] = "$Id$";
+
+#include <stdio.h>
+#include "b.h"
+
+int prevent_divergence = 0;
+
+List chainrules;
+
+void
+findChainRules()
+{
+	List pl;
+
+	assert(!chainrules);
+
+	for (pl = rules; pl; pl = pl->next) {
+		Rule p = (Rule) pl->x;
+		if (!p->pat->op) {
+			chainrules = newList(p, chainrules);
+		} else {
+			p->pat->op->table->rules = newList(p, p->pat->op->table->rules);
+			addRelevant(p->pat->op->table->relevant, p->lhs->num);
+		}
+	}
+}
+
+void
+zero(t) Item_Set t;
+{
+	int i;
+	DeltaCost base;
+	int exists;
+	int base_nt;
+
+	assert(!t->closed);
+
+	ZEROCOST(base);
+	exists = 0;
+	for (i = 0; i < max_nonterminal; i++) {
+		if (t->virgin[i].rule) {
+			if (exists) {
+				if (LESSCOST(t->virgin[i].delta, base)) {
+					ASSIGNCOST(base, t->virgin[i].delta);
+					base_nt = i;
+				}
+			} else {
+				ASSIGNCOST(base, t->virgin[i].delta);
+				exists = 1;
+				base_nt = i;
+			}
+		}
+	}
+	if (!exists) {
+		return;
+	}
+	for (i = 0; i < max_nonterminal; i++) {
+		if (t->virgin[i].rule) {
+			MINUSCOST(t->virgin[i].delta, base);
+		}
+		NODIVERGE(t->virgin[i].delta, t, i, base_nt);
+	}
+}
+
+void
+closure(t) Item_Set t;
+{
+	int changes;
+	List pl;
+
+	assert(!t->closed);
+	t->closed = itemArrayCopy(t->virgin);
+
+	changes = 1;
+	while (changes) {
+		changes = 0;
+		for (pl = chainrules; pl; pl = pl->next) {
+			Rule p = (Rule) pl->x;
+			register Item *rhs_item = &t->closed[p->pat->children[0]->num];
+
+			if (rhs_item->rule) {	/* rhs is active */
+				DeltaCost dc;
+				register Item *lhs_item = &t->closed[p->lhs->num];
+
+				ASSIGNCOST(dc, rhs_item->delta);
+				ADDCOST(dc, p->delta);
+				if (LESSCOST(dc, lhs_item->delta) || !lhs_item->rule) {
+					ASSIGNCOST(lhs_item->delta, dc);
+					lhs_item->rule = p;
+					changes = 1;
+				}
+			}
+		}
+	}
+}
diff --git a/llvm/utils/Burg/delta.c b/llvm/utils/Burg/delta.c
new file mode 100644
index 00000000000..d79654910fc
--- /dev/null
+++ b/llvm/utils/Burg/delta.c
@@ -0,0 +1,143 @@
+char rcsid_delta[] = "$Id$";
+
+#include <stdio.h>
+#include "b.h"
+#include "fe.h"
+
+int principleCost = 0;
+int lexical = 0;
+
+#ifndef NOLEX
+void
+ASSIGNCOST(l, r) DeltaPtr l; DeltaPtr r;
+{
+	int i;
+
+	if (lexical) {
+		for (i = 0; i < DELTAWIDTH; i++) {
+			l[i] = r[i];
+		}
+	} else {
+			l[0] = r[0];
+	}
+}
+
+void
+ADDCOST(l, r) DeltaPtr l; DeltaPtr r;
+{
+	int i;
+
+	if (lexical) {
+		for (i = 0; i < DELTAWIDTH; i++) {
+			l[i] += r[i];
+		}
+	} else {
+		l[0] += r[0];
+	}
+}
+
+void
+MINUSCOST(l, r) DeltaPtr l; DeltaPtr r;
+{
+	int i;
+
+	if (lexical) {
+		for (i = 0; i < DELTAWIDTH; i++) {
+			l[i] -= r[i];
+		}
+	} else {
+		l[0] -= r[0];
+	}
+}
+
+void
+ZEROCOST(x) DeltaPtr x;
+{
+	int i;
+
+	if (lexical) {
+		for (i = 0; i < DELTAWIDTH; i++) {
+			x[i] = 0;
+		}
+	} else {
+		x[0] = 0;
+	}
+}
+
+int
+LESSCOST(l, r) DeltaPtr l; DeltaPtr r;
+{
+	int i;
+
+	if (lexical) {
+		for (i = 0; i < DELTAWIDTH; i++) {
+			if (l[i] < r[i]) {
+				return 1;
+			} else if (l[i] > r[i]) {
+				return 0;
+			}
+		}
+		return 0;
+	} else {
+		return l[0] < r[0];
+	}
+}
+
+int
+EQUALCOST(l, r) DeltaPtr l; DeltaPtr r;
+{
+	int i;
+
+	if (lexical) {
+		for (i = 0; i < DELTAWIDTH; i++) {
+			if (l[i] != r[i]) {
+				return 0;
+			}
+		}
+		return 1;
+	} else {
+		return l[0] == r[0];
+	}
+}
+#endif /* NOLEX */
+
+void
+CHECKDIVERGE(c, its, nt, base) DeltaPtr c; Item_Set its; int nt; int base;
+{
+	int i;
+
+	if (prevent_divergence <= 0) {
+		return;
+	}
+	if (lexical) {
+#ifndef NOLEX
+		for (i = 0; i < DELTAWIDTH; i++) {
+			if (c[i] > prevent_divergence) {
+				char ntname[100];
+				char basename[100];
+				nonTerminalName(ntname, nt);
+				nonTerminalName(basename, base);
+				fprintf(stderr, "ERROR:  The grammar appears to diverge\n");
+				fprintf(stderr, "\tRelative Costs: %s(0), %s(%d)\n", basename, ntname, c[i]);
+				fprintf(stderr, "\tOffending Operator: %s\n", its->op->name);
+				fprintf(stderr, "\tOffending Tree: ");
+				printRepresentative(stderr, its);
+				fprintf(stderr, "\n");
+				exit(1);
+			}
+		}
+#endif /*NOLEX*/
+	} else if (PRINCIPLECOST(c) > prevent_divergence) {
+		char ntname[100];
+		char basename[100];
+		nonTerminalName(ntname, nt);
+		nonTerminalName(basename, base);
+		fprintf(stderr, "ERROR:  The grammar appears to diverge\n");
+		fprintf(stderr, "\tRelative Costs: %s(0), %s(%d)\n", basename, ntname, PRINCIPLECOST(c));
+		fprintf(stderr, "\tOffending Operator: %s\n", its->op->name);
+		fprintf(stderr, "\tOffending Tree: ");
+		printRepresentative(stderr, its);
+		fprintf(stderr, "\n");
+		exit(1);
+	}
+}
diff --git a/llvm/utils/Burg/fe.c b/llvm/utils/Burg/fe.c
new file mode 100644
index 00000000000..36b373dd650
--- /dev/null
+++ b/llvm/utils/Burg/fe.c
@@ -0,0 +1,403 @@
+char rcsid_fe[] = "$Id$";
+
+#include <stdio.h>
+#include <string.h>
+#include "b.h"
+#include "fe.h"
+
+int grammarflag;
+
+static int arity;
+
+List	ruleASTs;
+List	grammarNts;
+
+static void doBinding ARGS((Binding));
+static void doDecl ARGS((Arity));
+static NonTerminal lookup ARGS((Pattern));
+static NonTerminal normalize ARGS((PatternAST, NonTerminal, Pattern *));
+static void doEnterNonTerm ARGS((RuleAST));
+static void doRule ARGS((RuleAST));
+static void doTable ARGS((Operator));
+
+static void
+doBinding(b) Binding b;
+{
+	int new;
+	Symbol s;
+
+	s = enter(b->name, &new);
+	if (!new) {
+		fprintf(stderr, "Non-unique name: %s\n", b->name);
+		exit(1);
+	}
+	s->tag = OPERATOR;
+	s->u.op = newOperator(b->name, b->opnum, arity);
+	if (arity == 0) {
+		leaves = newList(s->u.op, leaves);
+	}
+}
+
+static void
+doDecl(a) Arity a;
+{
+	if (!a) {
+		return;
+	}
+	arity = a->arity;
+	foreachList((ListFn) doBinding, a->bindings);
+}
+
+
+static List xpatterns;
+static int tcount;
+
+static NonTerminal
+lookup(p) Pattern p;
+{
+	char buf[10];
+	char *s;
+	List l;
+	NonTerminal n;
+	DeltaCost dummy;
+
+	for (l = xpatterns; l; l = l->next) {
+		Pattern x = (Pattern) l->x;
+		if (x->op == p->op 
+				&& x->children[0] == p->children[0]
+				&& x->children[1] == p->children[1]) {
+			return x->normalizer;
+		}
+	}
+	sprintf(buf, "n%%%d", tcount++);
+	s = (char *) zalloc(strlen(buf)+1);
+	strcpy(s, buf);
+	n = newNonTerminal(s);
+	p->normalizer = n;
+	xpatterns = newList(p, xpatterns);
+	ZEROCOST(dummy);
+	(void) newRule(dummy, 0, n, p);
+	return n;
+}
+
+static NonTerminal
+normalize(ast, nt, patt) PatternAST ast; NonTerminal nt; Pattern *patt;
+{
+	Symbol s;
+	int new;
+	Pattern dummy;
+
+	s = enter(ast->op, &new);
+	ast->sym = s;
+	if (new) { 
+		fprintf(stderr, "Illegal use of %s --- undefined symbol\n", s->name);
+		exit(1);
+		return 0; /* shut up compilers */
+	} else if (s->tag == NONTERMINAL) {
+		if (ast->children) {
+			fprintf(stderr, "Illegal use of %s, a non-terminal, as a terminal\n", s->name);
+			exit(1);
+		}
+		*patt = newPattern(0);
+		(*patt)->children[0] = s->u.nt;
+		return s->u.nt;
+	} else {
+		s->u.op->ref = 1;
+		*patt = newPattern(s->u.op);
+		if (s->u.op->arity == -1) {
+			if (!ast->children) {
+				s->u.op->arity = 0;
+				leaves = newList(s->u.op, leaves);
+			} else if (!ast->children->next) {
+				s->u.op->arity = 1;
+			} else if (!ast->children->next->next) {
+				s->u.op->arity = 2;
+			} else {
+				fprintf(stderr, "ERROR: Too many children (max = 2) for \"%s\"\n", s->name);
+				exit(1);
+			}
+			if (s->u.op->arity > max_arity) {
+				max_arity = s->u.op->arity;
+			}
+		}
+		switch (s->u.op->arity) {
+		default:
+			assert(0);
+			break;
+		case 0:
+			if (ast->children) {
+				fprintf(stderr, "ERROR: Incorrect number of children for leaf operator, \"%s\"\n", s->name);
+				exit(1);
+			}
+			break;
+		case 1:
+			if (!ast->children || ast->children->next) {
+				fprintf(stderr, "ERROR: Incorrect number of children for unary operator, \"%s\"\n", s->name);
+				exit(1);
+			}
+			(*patt)->children[0] = normalize((PatternAST) ast->children->x, 0, &dummy);
+			break;
+		case 2:
+			if (!ast->children || !ast->children->next) {
+				fprintf(stderr, "ERROR: Incorrect number of children for binary operator, \"%s\"\n", s->name);
+				exit(1);
+			}
+			(*patt)->children[0] = normalize((PatternAST) ast->children->x, 0, &dummy);
+			(*patt)->children[1] = normalize((PatternAST) ast->children->next->x, 0, &dummy);
+			break;
+		}
+		if (nt) {
+			(*patt)->normalizer = nt;
+			return nt;
+		} else {
+			return lookup(*patt);
+		}
+	}
+}
+
+static void
+doEnterNonTerm(ast) RuleAST ast;
+{
+	int new;
+	Symbol s;
+	DeltaCost delta;
+	int i;
+	IntList p;
+
+
+	s = enter(ast->lhs, &new);
+	if (new) {
+		s->u.nt = newNonTerminal(s->name);
+		s->tag = NONTERMINAL;
+	} else {
+		if (s->tag != NONTERMINAL) {
+			fprintf(stderr, "Illegal use of %s as a non-terminal\n", s->name);
+			exit(1);
+		}
+	}
+	ZEROCOST(delta);
+	for (p = ast->cost, i = 0; p; p = p->next, i++) {
+		int x = p->x;
+#ifndef NOLEX
+		if (lexical) {
+			if (i < DELTAWIDTH) {
+				delta[i] = x;
+			}
+		} else 
+#endif /* NOLEX */
+		{
+			if (i == principleCost) {
+				PRINCIPLECOST(delta) = x;
+			}
+		}
+	}
+	ast->rule = newRule(delta, ast->erulenum, s->u.nt, 0);
+}
+
+static void
+doRule(ast) RuleAST ast;
+{
+	Pattern pat;
+
+	(void) normalize(ast->pat, ast->rule->lhs, &pat);
+	ast->rule->pat = pat;
+}
+
+static void
+doTable(op) Operator op;
+{
+	op->table = newTable(op);
+}
+
+void 
+doSpec(decls, rules) List decls; List rules;
+{
+	foreachList((ListFn) doDecl, decls);
+	debug(debugTables, foreachList((ListFn) dumpOperator_l, operators));
+
+	ruleASTs = rules;
+	reveachList((ListFn) doEnterNonTerm, rules);
+
+	last_user_nonterminal = max_nonterminal;
+
+	reveachList((ListFn) doRule, rules);
+	debug(debugTables, foreachList((ListFn) dumpRule, rules));
+
+	foreachList((ListFn) doTable, operators);
+}
+
+void
+doStart(name) char *name;
+{
+	Symbol s;
+	int new;
+
+	if (start) {
+		yyerror1("Redeclaration of start symbol to be ");
+		fprintf(stderr, "\"%s\"\n", name);
+		exit(1);
+	}
+	s = enter(name, &new);
+	if (new) {
+		s->u.nt = newNonTerminal(s->name);
+		s->tag = NONTERMINAL;
+	} else {
+		if (s->tag != NONTERMINAL) {
+			fprintf(stderr, "Illegal use of %s as a non-terminal\n", s->name);
+			exit(1);
+		}
+	}
+}
+
+void
+doGrammarNts()
+{
+	List l;
+	int new;
+
+	for (l = grammarNts; l; l = l->next) {
+		char *n = (char*) l->x;
+		Symbol s;
+
+		s = enter(n, &new);
+		if (new) {
+			fprintf(stderr, "ERROR: %%gram, unused non-terminal: \"%s\"\n", n);
+			exit(1);
+		}
+		if (s->tag != NONTERMINAL) {
+			fprintf(stderr, "ERROR: %%gram, Not a non-terminal: \"%s\"\n", n);
+			exit(1);
+		}
+		l->x = s;
+	}
+}
+
+void
+doGram(nts) List nts;
+{
+	if (grammarNts) {
+		yyerror1("Redeclaration of %%gram\n");
+		exit(1);
+	}
+	grammarNts = nts;
+}
+
+Arity 
+newArity(ar, b) int ar; List b;
+{
+	Arity a = (Arity) zalloc(sizeof(struct arity));
+	a->arity = ar;
+	a->bindings = b;
+	return a;
+}
+
+Binding 
+newBinding(name, opnum) char *name; int opnum;
+{
+	Binding b = (Binding) zalloc(sizeof(struct binding));
+	if (opnum == 0) {
+		yyerror1("ERROR: Non-positive external symbol number, ");
+		fprintf(stderr, "%d", opnum);
+		exit(1);
+	}
+	b->name = name;
+	b->opnum = opnum;
+	return b;
+}
+
+PatternAST
+newPatternAST(op, children) char *op; List children;
+{
+	PatternAST p = (PatternAST) zalloc(sizeof(struct patternAST));
+	p->op = op;
+	p->children = children;
+	return p;
+}
+
+int max_ruleAST;
+
+RuleAST
+newRuleAST(lhs, pat, erulenum, cost) char *lhs; PatternAST pat; int erulenum; IntList cost;
+{
+	RuleAST p = (RuleAST) zalloc(sizeof(struct ruleAST));
+	p->lhs = lhs;
+	p->pat = pat;
+	if (erulenum <= 0) {
+		yyerror1("External Rulenumber ");
+		fprintf(stderr, "(%d) <= 0\n", erulenum);
+		exit(1);
+	}
+	p->erulenum = erulenum;
+	p->cost = cost;
+	max_ruleAST++;
+	return p;
+}
+
+void
+dumpBinding(b) Binding b;
+{
+	printf("%s=%d ", b->name, b->opnum);
+}
+
+void
+dumpArity(a) Arity a;
+{
+	List l;
+
+	printf("Arity(%d) ", a->arity);
+	for (l = a->bindings; l; l = l->next) {
+		Binding b = (Binding) l->x;
+		dumpBinding(b);
+	}
+	printf("\n");
+}
+
+void
+dumpPatternAST(p) PatternAST p;
+{
+	List l;
+
+	printf("%s", p->op);
+	if (p->children) {
+		printf("(");
+		for (l = p->children; l; l = l->next) {
+			PatternAST past = (PatternAST) l->x;
+			dumpPatternAST(past);
+			if (l->next) {
+				printf(", ");
+			}
+		}
+		printf(")");
+	}
+}
+
+void
+dumpRuleAST(p) RuleAST p;
+{
+	printf("%s : ", p->lhs);
+	dumpPatternAST(p->pat);
+	printf(" = %d (%ld)\n", p->erulenum, (long) p->cost);
+}
+
+void
+dumpDecls(decls) List decls;
+{
+	List l;
+
+	for (l = decls; l; l = l->next) {
+		Arity a = (Arity) l->x;
+		dumpArity(a);
+	}
+}
+
+void
+dumpRules(rules) List rules;
+{
+	List l;
+
+	for (l = rules; l; l = l->next) {
+		RuleAST p = (RuleAST) l->x;
+		dumpRuleAST(p);
+	}
+}
+
diff --git a/llvm/utils/Burg/fe.h b/llvm/utils/Burg/fe.h
new file mode 100644
index 00000000000..1c7b2fecbf3
--- /dev/null
+++ b/llvm/utils/Burg/fe.h
@@ -0,0 +1,132 @@
+/* $Id$ */
+
+struct binding {
+	char	*name;
+	int	opnum;
+};
+typedef struct binding	*Binding;
+
+struct arity {
+	int	arity;
+	List	bindings;
+};
+typedef struct arity	*Arity;
+
+struct patternAST {
+	struct symbol *sym;
+	char	*op;
+	List	children;
+};
+typedef struct patternAST	*PatternAST;
+
+struct ruleAST {
+	char			*lhs;
+	PatternAST		pat;
+	int			erulenum;
+	IntList			cost;
+	struct rule		*rule;
+	struct strTableElement	*kids;
+	struct strTableElement	*nts;
+};
+typedef struct ruleAST	*RuleAST;
+
+typedef enum {
+	UNKNOWN,
+	OPERATOR,
+	NONTERMINAL
+} TagType;
+
+struct symbol {
+	char	*name;
+	TagType	tag;
+	union {
+		NonTerminal	nt;
+		Operator	op;
+	} u;
+};
+typedef struct symbol	*Symbol;
+
+struct strTableElement {
+	char *str;
+	IntList erulenos;
+	char *ename;
+};
+typedef struct strTableElement	*StrTableElement;
+
+struct strTable {
+	List elems;
+};
+typedef struct strTable	*StrTable;
+
+extern void doGrammarNts ARGS((void));
+void makeRuleDescArray ARGS((void));
+void makeDeltaCostArray ARGS((void));
+void makeStateStringArray ARGS((void));
+
+extern StrTable newStrTable ARGS((void));
+extern StrTableElement addString ARGS((StrTable, char *, int, int *));
+
+extern void doSpec ARGS((List, List));
+extern Arity newArity ARGS((int, List));
+extern Binding newBinding ARGS((char *, int));
+extern PatternAST newPatternAST ARGS((char *, List));
+extern RuleAST newRuleAST ARGS((char *, PatternAST, int, IntList));
+extern Symbol enter ARGS((char *, int *));
+extern Symbol newSymbol ARGS((char *));
+
+extern void makeDebug ARGS((void));
+extern void makeSimple ARGS((void));
+extern void makePlanks ARGS((void));
+extern void makeOpLabel ARGS((void));
+extern void makeChild ARGS((void));
+extern void makeOperators ARGS((void));
+extern void makeLabel ARGS((void));
+extern void makeString ARGS((void));
+extern void makeString ARGS((void));
+extern void makeReduce ARGS((void));
+extern void makeRuleTable ARGS((void));
+extern void makeTables ARGS((void));
+extern void makeTreecost ARGS((void));
+extern void makePrint ARGS((void));
+extern void makeRule ARGS((void));
+extern void makeNts ARGS((void));
+extern void makeKids ARGS((void));
+extern void startBurm ARGS((void));
+extern void startOptional ARGS((void));
+extern void makePlankLabel ARGS((void));
+extern void makeStateLabel ARGS((void));
+extern void makeStringArray ARGS((void));
+extern void makeNonterminalArray ARGS((void));
+extern void makeCostArray ARGS((void));
+extern void makeLHSmap ARGS((void));
+extern void makeClosureArray ARGS((void));
+extern void makeOperatorVector ARGS((void));
+extern void endOptional ARGS((void));
+extern void reportDiagnostics ARGS((void));
+extern void makeNonterminals ARGS((void));
+extern int opsOfArity ARGS((int));
+
+extern void yypurge ARGS((void));
+extern void yyfinished ARGS((void));
+
+extern void printRepresentative ARGS((FILE *, Item_Set));
+
+extern void dumpRules ARGS((List));
+extern void dumpDecls ARGS((List));
+extern void dumpRuleAST ARGS((RuleAST));
+extern void dumpPatternAST ARGS((PatternAST));
+extern void dumpArity ARGS((Arity));
+extern void dumpBinding ARGS((Binding));
+extern void dumpStrTable ARGS((StrTable));
+
+extern int yylex ARGS((void));
+extern int yyparse ARGS((void));
+
+extern int	max_ruleAST;
+extern List	ruleASTs;
+
+extern FILE	*outfile;
+extern const char *prefix;
+extern int 	trimflag;
+extern int 	speedflag;
+extern int 	grammarflag;
diff --git a/llvm/utils/Burg/gram.yc b/llvm/utils/Burg/gram.yc
new file mode 100644
index 00000000000..9d2f9f4e53f
--- /dev/null
+++ b/llvm/utils/Burg/gram.yc
@@ -0,0 +1,91 @@
+%{
+char rcsid_gram[] = "$Id$";
+
+#include <stdio.h>
+#include "b.h"
+#include "fe.h"
+int doGram(List);
+%}
+
+%union {
+	int y_int;
+	char *y_string;
+	Arity y_arity;
+	Binding y_binding;
+	PatternAST y_patternAST;
+	RuleAST y_ruleAST;
+	List y_list;
+	IntList y_intlist;
+}
+
+%start full
+
+%term ERROR
+%term K_TERM
+%term K_GRAM
+%term K_START
+%term K_PPERCENT
+%term INT
+%term ID
+
+%token <y_string> ID
+%token <y_int> INT
+
+%type <y_arity> decl
+%type <y_binding> binding
+%type <y_intlist> cost costtail
+%type <y_ruleAST> rule
+%type <y_patternAST> pattern
+%type <y_list> decls rules bindinglist grammarlist
+%%
+
+
+full	: spec
+	| spec K_PPERCENT
+		{ yyfinished(); }
+	;
+
+spec	: decls K_PPERCENT rules
+		{ doSpec($1, $3); }
+	;
+
+decls	: /* lambda */	{ $$ = 0; }
+	| decls decl	{ $$ = newList($2, $1); }
+	;
+
+decl	: K_TERM bindinglist	{ $$ = newArity(-1, $2); }
+	| K_GRAM grammarlist	{ $$ = 0; doGram($2); }
+	| K_START ID		{ $$ = 0; doStart($2); }	/* kludge */
+	;
+
+grammarlist	: /* lambda */		{ $$ = 0; }
+		| grammarlist ID	{ $$ = newList($2, $1); }
+		;
+
+bindinglist	: /* lambda */		{ $$ = 0; }
+		| bindinglist binding	{ $$ = newList($2, $1); }
+		;
+
+binding	: ID '=' INT	{ $$ = newBinding($1, $3); }
+	;
+
+rules	: /* lambda */	{ $$ = 0; }
+	| rules rule	{ $$ = newList($2, $1); }
+	;
+
+rule	: ID ':' pattern '=' INT cost ';'	{ $$ = newRuleAST($1, $3, $5, $6); }
+		;
+
+pattern	: ID 					{ $$ = newPatternAST($1, 0); }
+	| ID '(' pattern ')'			{ $$ = newPatternAST($1, newList($3,0)); }
+	| ID '(' pattern ',' pattern ')'	{ $$ = newPatternAST($1, newList($3, newList($5, 0))); }
+	;
+
+cost	: /* lambda */		{ $$ = 0; }
+	| '(' INT costtail ')'	{ $$ = newIntList($2, $3); }
+	;
+
+costtail	: /* lambda */		{ $$ = 0; }
+		| ',' INT costtail	{ $$ = newIntList($2, $3); }
+		| INT costtail		{ $$ = newIntList($1, $2); }
+		;
diff --git a/llvm/utils/Burg/item.c b/llvm/utils/Burg/item.c
new file mode 100644
index 00000000000..4a9f4a320b6
--- /dev/null
+++ b/llvm/utils/Burg/item.c
@@ -0,0 +1,133 @@
+char rcsid_item[] = "$Id$";
+
+#include "b.h"
+#include <stdio.h>
+#include <string.h>
+#include "fe.h"
+
+static Item_Set fptr;
+
+ItemArray
+newItemArray()
+{
+	ItemArray ia;
+	ia = (ItemArray) zalloc(max_nonterminal *sizeof(*ia));
+	return ia;
+}
+
+ItemArray
+itemArrayCopy(src) ItemArray src;
+{
+	ItemArray dst;
+
+	dst = newItemArray();
+	memcpy(dst, src, max_nonterminal * sizeof(*dst));
+	return dst;
+}
+
+Item_Set
+newItem_Set(relevant) Relevant relevant;
+{
+	Item_Set ts;
+	
+	if (fptr) {
+		ts = fptr;
+		fptr = 0;
+		memset(ts->virgin, 0, max_nonterminal * sizeof(struct item));
+		if (ts->closed) {
+			zfree(ts->closed);
+			ts->closed = 0;
+		}
+		ts->num = 0;
+		ts->op = 0;
+	} else {
+		ts = (Item_Set) zalloc(sizeof(struct item_set));
+		ts->virgin = newItemArray();
+	}
+	ts->relevant = relevant;
+	return ts;
+}
+
+void
+freeItem_Set(ts) Item_Set ts;
+{
+	assert(!fptr);
+	fptr = ts;
+}
+
+int
+equivSet(a, b) Item_Set a; Item_Set b;
+{
+	register Relevant r;
+	register int nt;
+	register Item *aa = a->virgin;
+	register Item *ba = b->virgin;
+
+	/*
+	return !bcmp(a->virgin, b->virgin, max_nonterminal * sizeof(Item));
+	*/
+
+	r = a->relevant ? a->relevant : b->relevant;
+	assert(r);
+
+	if (a->op && b->op && a->op != b->op) {
+		return 0;
+	}
+	for (; (nt = *r) != 0; r++) {
+		if (aa[nt].rule != ba[nt].rule || !EQUALCOST(aa[nt].delta, ba[nt].delta)) {
+			return 0;
+		}
+	}
+	return 1;
+}
+
+void
+printRepresentative(f, s) FILE *f; Item_Set s;
+{
+	if (!s) {
+		return;
+	}
+	fprintf(f, "%s", s->op->name);
+	switch (s->op->arity) {
+	case 1:
+		fprintf(f, "(");
+		printRepresentative(f, s->kids[0]);
+		fprintf(f, ")");
+		break;
+	case 2:
+		fprintf(f, "(");
+		printRepresentative(f, s->kids[0]);
+		fprintf(f, ", ");
+		printRepresentative(f, s->kids[1]);
+		fprintf(f, ")");
+		break;
+	}
+}
+
+void
+dumpItem(t) Item *t;
+{
+	printf("[%s #%d]", t->rule->lhs->name, t->rule->num);
+	dumpCost(t->delta);
+}
+
+void
+dumpItem_Set(ts) Item_Set ts;
+{
+	int i;
+
+	printf("Item_Set #%d: [", ts->num);
+	for (i = 1; i < max_nonterminal; i++) {
+		if (ts->virgin[i].rule) {
+			printf(" %d", i);
+			dumpCost(ts->virgin[i].delta);
+		}
+	}
+	printf(" ]\n");
+}
+
+void
+dumpCost(dc) DeltaCost dc;
+{
+	printf("(%ld)", (long) dc);
+}
diff --git a/llvm/utils/Burg/lex.c b/llvm/utils/Burg/lex.c
new file mode 100644
index 00000000000..85eb8a738fa
--- /dev/null
+++ b/llvm/utils/Burg/lex.c
@@ -0,0 +1,259 @@
+char rcsid_lex[] = "$Id$";
+
+#include <ctype.h>
+#include <stdio.h>
+#include <string.h>
+#include "b.h"
+#include "fe.h"
+#include "gram.tab.h"
+
+static char buf[BUFSIZ];
+
+static int yyline = 1;
+
+typedef int (*ReadFn) ARGS((void));
+
+static char *StrCopy ARGS((char *));
+static int code_get ARGS((void));
+static int simple_get ARGS((void));
+static void ReadCharString ARGS((ReadFn, int));
+static void ReadCodeBlock ARGS((void));
+static void ReadOldComment ARGS((ReadFn));
+
+static char *
+StrCopy(s) char *s;
+{
+	char *t = (char *)zalloc(strlen(s) + 1);
+	strcpy(t,s);
+	return t;
+}
+
+static int
+simple_get()
+{
+	int ch;
+	if ((ch = getchar()) == '\n') {
+		yyline++;
+	}
+	return ch;
+}
+
+static int
+code_get()
+{
+	int ch;
+	if ((ch = getchar()) == '\n') {
+		yyline++;
+	}
+	if (ch != EOF) {
+		fputc(ch, outfile);
+	}
+	return ch;
+}
+
+void
+yypurge()
+{
+	while (code_get() != EOF) ;
+}
+
+
+static void
+ReadCharString(rdfn, which) ReadFn rdfn; int which;
+{
+	int ch;
+	int backslash = 0;
+	int firstline = yyline;
+
+	while ((ch = rdfn()) != EOF) {
+		if (ch == which && !backslash) {
+			return;
+		}
+		if (ch == '\\' && !backslash) {
+			backslash = 1;
+		} else {
+			backslash = 0;
+		}
+	}
+	yyerror1("Unexpected EOF in string on line ");
+	fprintf(stderr, "%d\n", firstline);
+	exit(1);
+}
+
+static void
+ReadOldComment(rdfn) ReadFn rdfn;
+{
+	/* will not work for comments delimiter in string */
+
+	int ch;
+	int starred = 0;
+	int firstline = yyline;
+
+	while ((ch = rdfn()) != EOF) {
+		if (ch == '*') {
+			starred = 1;
+		} else if (ch == '/' && starred) {
+			return;
+		} else {
+			starred = 0;
+		}
+	}
+	yyerror1("Unexpected EOF in comment on line ");
+	fprintf(stderr, "%d\n", firstline);
+	exit(1);
+}
+
+static void
+ReadCodeBlock()
+{
+	int ch;
+	int firstline = yyline;
+
+	while ((ch = getchar()) != EOF) {
+		if (ch == '%') {
+			ch = getchar();
+			if (ch != '}') {
+				yyerror("bad %%");
+			}
+			return;
+		}
+		fputc(ch, outfile);
+		if (ch == '\n') {
+			yyline++;
+		}
+		if (ch == '"' || ch == '\'') {
+			ReadCharString(code_get, ch);
+		} else if (ch == '/') {
+			ch = getchar();
+			if (ch == '*') {
+				fputc(ch, outfile);
+				ReadOldComment(code_get);
+				continue;
+			} else {
+				ungetc(ch, stdin);
+			}
+		}
+	}
+	yyerror1("Unclosed block of C code started on line ");
+	fprintf(stderr, "%d\n", firstline);
+	exit(1);
+}
+
+static int done;
+void
+yyfinished()
+{
+	done = 1;
+}
+
+int
+yylex()
+{
+	int ch;
+	char *ptr = buf;
+
+	if (done) return 0;
+	while ((ch = getchar()) != EOF) {
+		switch (ch) {
+		case ' ':
+		case '\f':
+		case '\t':
+			continue;
+		case '\n':
+			yyline++;
+			continue;
+		case '(':
+		case ')':
+		case ',':
+		case ':':
+		case ';':
+		case '=':
+			return(ch);
+		case '/':
+			ch = getchar();
+			if (ch == '*') {
+				ReadOldComment(simple_get);
+				continue;
+			} else {
+				ungetc(ch, stdin);
+				yyerror("illegal char /");
+				continue;
+			}
+		case '%':
+			ch = getchar();
+			switch (ch) {
+			case '%':
+				return (K_PPERCENT);
+			case '{':
+				ReadCodeBlock();
+				continue;
+			case 's':
+			case 'g':
+			case 't':
+				do {
+					if (ptr >= &buf[BUFSIZ]) {
+						yyerror("ID too long");
+						return(ERROR);
+					} else {
+						*ptr++ = ch;
+					}
+					ch = getchar();
+				} while (isalpha(ch) || isdigit(ch) || ch == '_');
+				ungetc(ch, stdin);
+				*ptr = '\0';
+				if (!strcmp(buf, "term")) return K_TERM;
+				if (!strcmp(buf, "start")) return K_START;
+				if (!strcmp(buf, "gram")) return K_GRAM;
+				yyerror("illegal character after %%");
+				continue;
+			default:
+				yyerror("illegal character after %%");
+				continue;
+			}
+		default:
+			if (isalpha(ch) ) {
+				do {
+					if (ptr >= &buf[BUFSIZ]) {
+						yyerror("ID too long");
+						return(ERROR);
+					} else {
+						*ptr++ = ch;
+					}
+					ch = getchar();
+				} while (isalpha(ch) || isdigit(ch) || ch == '_');
+				ungetc(ch, stdin);
+				*ptr = '\0';
+				yylval.y_string = StrCopy(buf);
+				return(ID);
+			} 
+			if (isdigit(ch)) {
+				int val=0;
+				do {
+					val *= 10;
+					val += (ch - '0');
+					ch = getchar();
+				} while (isdigit(ch));
+				ungetc(ch, stdin);
+				yylval.y_int = val;
+				return(INT);
+			}
+			yyerror1("illegal char ");
+			fprintf(stderr, "(\\%03o)\n", ch);
+			exit(1);
+		}
+	}
+	return(0);
+}
+
+void yyerror1(const char *str)
+{
+	fprintf(stderr, "line %d: %s", yyline, str);
+}
+
+void
+yyerror(const char *str)
+{
+	yyerror1(str);
+	fprintf(stderr, "\n");
+	exit(1);
+}
diff --git a/llvm/utils/Burg/list.c b/llvm/utils/Burg/list.c
new file mode 100644
index 00000000000..d3eefa27d09
--- /dev/null
+++ b/llvm/utils/Burg/list.c
@@ -0,0 +1,75 @@
+char rcsid_list[] = "$Id$";
+
+#include "b.h"
+
+IntList
+newIntList(x, next) int x; IntList next;
+{
+	IntList l;
+
+	l = (IntList) zalloc(sizeof(*l));
+	assert(l);
+	l->x = x;
+	l->next = next;
+
+	return l;
+}
+
+List
+newList(x, next) void *x; List next;
+{
+	List l;
+
+	l = (List) zalloc(sizeof(*l));
+	assert(l);
+	l->x = x;
+	l->next = next;
+
+	return l;
+}
+
+List
+appendList(x, l) void *x; List l;
+{
+	List last;
+	List p;
+
+	last = 0;
+	for (p = l; p; p = p->next) {
+		last = p;
+	}
+	if (last) {
+		last->next = newList(x, 0);
+		return l;
+	} else {
+		return newList(x, 0);
+	}
+}
+
+void
+foreachList(f, l) ListFn f; List l;
+{
+	for (; l; l = l->next) {
+		(*f)(l->x);
+	}
+}
+
+void
+reveachList(f, l) ListFn f; List l;
+{
+	if (l) {
+		reveachList(f, l->next);
+		(*f)(l->x);
+	}
+}
+
+int
+length(l) List l;
+{
+	int c = 0;
+
+	for(; l; l = l->next) {
+		c++;
+	}
+	return c;
+}
diff --git a/llvm/utils/Burg/main.c b/llvm/utils/Burg/main.c
new file mode 100644
index 00000000000..dbfdbf4faca
--- /dev/null
+++ b/llvm/utils/Burg/main.c
@@ -0,0 +1,182 @@
+char rcsid_main[] = "$Id$";
+
+#include <math.h>
+#include <stdio.h>
+#include "b.h"
+#include "fe.h"
+
+int debugTables = 0;
+static int simpleTables = 0;
+static int internals = 0;
+static int diagnostics = 0;
+
+static char *inFileName;
+static char *outFileName;
+
+static char version[] = "BURG, Version 1.0";
+
+extern int main ARGS((int argc, char **argv));
+
+int
+main(argc, argv) int argc; char **argv;
+{
+	int i;
+	extern int atoi ARGS((char *));
+
+	for (i = 1; argv[i]; i++) {
+		char **needStr = 0;
+		int *needInt = 0;
+
+		if (argv[i][0] == '-') {
+			switch (argv[i][1]) {
+			case 'V':
+				fprintf(stderr, "%s\n", version);
+				break;
+			case 'p':
+				needStr = (char**)&prefix;
+				break;
+			case 'o':
+				needStr = &outFileName;
+				break;
+			case 'I':
+				internals = 1;
+				break;
+			case 'T':
+				simpleTables = 1;
+				break;
+			case '=':
+#ifdef NOLEX
+				fprintf(stderr, "'%s' was not compiled to support lexicographic ordering\n", argv[0]);
+#else
+				lexical = 1;
+#endif /* NOLEX */
+				break;
+			case 'O':
+				needInt = &principleCost;
+				break;
+			case 'c':
+				needInt = &prevent_divergence;
+				break;
+			case 'e':
+				needInt = &exceptionTolerance;
+				break;
+			case 'd':
+				diagnostics = 1;
+				break;
+			case 'S':
+				speedflag = 1;
+				break;
+			case 't':
+				trimflag = 1;
+				break;
+			case 'G':
+				grammarflag = 1;
+				break;
+			default:
+				fprintf(stderr, "Bad option (%s)\n", argv[i]);
+				exit(1);
+			}
+		} else {
+			if (inFileName) {
+				fprintf(stderr, "Unexpected Filename (%s) after (%s)\n", argv[i], inFileName);
+				exit(1);
+			}
+			inFileName = argv[i];
+		}
+		if (needInt || needStr) {
+			char *v;
+			char *opt = argv[i];
+
+			if (argv[i][2]) {
+				v = &argv[i][2];
+			} else {
+				v = argv[++i];
+				if (!v) {
+					fprintf(stderr, "Expection argument after %s\n", opt);
+					exit(1);
+				}
+			}
+			if (needInt) {
+				*needInt = atoi(v);
+			} else if (needStr) {
+				*needStr = v;
+			}
+		}
+	}
+
+	if (inFileName) {
+		if(freopen(inFileName, "r", stdin)==NULL) {
+			fprintf(stderr, "Failed opening (%s)", inFileName);
+			exit(1);
+		}
+	}
+
+	if (outFileName) {
+		if ((outfile = fopen(outFileName, "w")) == NULL) {
+			fprintf(stderr, "Failed opening (%s)", outFileName);
+			exit(1);
+		}
+	} else {
+		outfile = stdout;
+	}
+
+
+	yyparse();
+
+	if (!rules) {
+		fprintf(stderr, "ERROR: No rules present\n");
+		exit(1);
+	}
+
+	findChainRules();
+	findAllPairs();
+	doGrammarNts();
+	build();
+
+	debug(debugTables, foreachList((ListFn) dumpOperator_l, operators));
+	debug(debugTables, printf("---final set of states ---\n"));
+	debug(debugTables, dumpMapping(globalMap));
+
+
+	startBurm();
+	makeNts();
+	if (simpleTables) {
+		makeSimple();
+	} else {
+		makePlanks();
+	}
+
+	startOptional();
+	makeLabel();
+	makeKids();
+
+	if (internals) {
+		makeChild();
+		makeOpLabel();
+		makeStateLabel();
+	}
+	endOptional();
+
+	makeOperatorVector();
+	makeNonterminals();
+	if (internals) {
+		makeOperators();
+		makeStringArray();
+		makeRuleDescArray();
+		makeCostArray();
+		makeDeltaCostArray();
+		makeStateStringArray();
+		makeNonterminalArray();
+		/*
+		makeLHSmap();
+		*/
+	}
+	makeClosureArray();
+
+	if (diagnostics) {
+		reportDiagnostics();
+	}
+
+	yypurge();
+	exit(0);
+}
diff --git a/llvm/utils/Burg/map.c b/llvm/utils/Burg/map.c
new file mode 100644
index 00000000000..588b485eab2
--- /dev/null
+++ b/llvm/utils/Burg/map.c
@@ -0,0 +1,135 @@
+char rcsid_map[] = "$Id$";
+
+#include <stdio.h>
+#include <string.h>
+#include "b.h"
+#include "fe.h"
+
+Mapping globalMap;
+
+static void growMapping ARGS((Mapping));
+static int hash ARGS((Item_Set, int));
+
+Mapping
+newMapping(size) int size;
+{
+	Mapping m;
+
+	m = (Mapping) zalloc(sizeof(struct mapping));
+	assert(m);
+
+	m->count = 0;
+	m->hash = (List*) zalloc(size * sizeof(List));
+	m->hash_size = size;
+	m->max_size = STATES_INCR;
+	m->set = (Item_Set*) zalloc(m->max_size * sizeof(Item_Set));
+	assert(m->set);
+
+	return m;
+}
+
+static void
+growMapping(m) Mapping m;
+{
+	Item_Set *tmp;
+
+	m->max_size += STATES_INCR;
+	tmp = (Item_Set*) zalloc(m->max_size * sizeof(Item_Set));
+	memcpy(tmp, m->set, m->count * sizeof(Item_Set));
+	zfree(m->set);
+	m->set = tmp;
+}
+
+static int
+hash(ts, mod) Item_Set ts; int mod;
+{
+	register Item *p = ts->virgin;
+	register int v;
+	register Relevant r = ts->relevant;
+	register int nt;
+
+	if (!ts->op) {
+		return 0;
+	}
+
+	v = 0;
+	for (; (nt = *r) != 0; r++) {
+		v ^= ((long)p[nt].rule) + (PRINCIPLECOST(p[nt].delta)<<4);
+	}
+	v >>= 4;
+	v &= (mod-1);
+	return v;
+}
+
+Item_Set
+encode(m, ts, new) Mapping m; Item_Set ts; int *new;
+{
+	int h;
+	List l;
+
+	assert(m);
+	assert(ts);
+	assert(m->count <= m->max_size);
+
+	if (grammarNts && errorState && m == globalMap) {
+		List l;
+		int found;
+
+		found = 0;
+		for (l = grammarNts; l; l = l->next) {
+			Symbol s;
+			s = (Symbol) l->x;
+
+			if (ts->virgin[s->u.nt->num].rule) {
+				found = 1;
+				break;
+			}
+		}
+		if (!found) {
+			*new = 0;
+			return errorState;
+		}
+	}
+
+	*new = 0;
+	h = hash(ts, m->hash_size);
+	for (l = m->hash[h]; l; l = l->next) {
+		Item_Set s = (Item_Set) l->x;
+		if (ts->op == s->op && equivSet(ts, s)) {
+			ts->num = s->num;
+			return s;
+		}
+	}
+	if (m->count >= m->max_size) {
+		growMapping(m);
+	}
+	assert(m->count < m->max_size);
+	m->set[m->count] = ts;
+	ts->num = m->count++;
+	*new = 1;
+	m->hash[h] = newList(ts, m->hash[h]);
+	return ts;
+}
+
+Item_Set
+decode(m, t) Mapping m; ItemSetNum t;
+{
+	assert(m);
+	assert(t);
+	assert(m->count < m->max_size);
+	assert(t < m->count);
+
+	return m->set[t];
+}
+
+void
+dumpMapping(m) Mapping m;
+{
+	int i;
+
+	printf("BEGIN Mapping: Size=%d\n", m->count);
+	for (i = 0; i < m->count; i++) {
+		dumpItem_Set(m->set[i]);
+	}
+	printf("END Mapping\n");
+}
diff --git a/llvm/utils/Burg/nonterminal.c b/llvm/utils/Burg/nonterminal.c
new file mode 100644
index 00000000000..71fd7d49442
--- /dev/null
+++ b/llvm/utils/Burg/nonterminal.c
@@ -0,0 +1,49 @@
+char rcsid_nonterminal[] = "$Id$";
+
+#include "b.h"
+#include <stdio.h>
+#include <string.h>
+
+NonTerminal	start;
+NonTerminalNum	max_nonterminal = 1;
+NonTerminalNum	last_user_nonterminal;
+List		nonterminals;
+
+NonTerminal
+newNonTerminal(name) char *name;
+{
+	NonTerminal nt;
+
+	nt = (NonTerminal) zalloc(sizeof(struct nonterminal));
+	assert(nt);
+	if (max_nonterminal == 1) {
+		start = nt;
+	}
+	nt->name = name;
+	nt->num = max_nonterminal++;
+	nonterminals = newList(nt, nonterminals);
+
+	return nt;
+}
+
+int
+nonTerminalName(buf, i) char *buf; int i;
+{
+	List l;
+
+	for (l = nonterminals; l; l = l->next) {
+		NonTerminal nt = (NonTerminal) l->x;
+		if (nt->num == i) {
+			strcpy(buf, nt->name);
+			return 1;
+		}
+	}
+	strcpy(buf, "(Unknown NonTerminal)");
+	return 0;
+}
+
+void
+dumpNonTerminal(n) NonTerminal n;
+{
+	printf("%s(%d)", n->name, n->num);
+}
diff --git a/llvm/utils/Burg/operator.c b/llvm/utils/Burg/operator.c
new file mode 100644
index 00000000000..a6df9e304df
--- /dev/null
+++ b/llvm/utils/Burg/operator.c
@@ -0,0 +1,48 @@
+char rcsid_operator[] = "$Id$";
+
+#include "b.h"
+#include <stdio.h>
+
+int max_arity = -1;
+
+List operators;
+List leaves;
+
+Operator
+newOperator(name, num, arity) char *name; OperatorNum num; ArityNum arity;
+{
+	Operator op;
+
+	assert(arity <= MAX_ARITY);
+	op = (Operator) zalloc(sizeof(struct operator));
+	assert(op);
+	op->name = name;
+	op->num = num;
+	op->arity = arity;
+
+	operators = newList(op, operators);
+
+	return op;
+}
+
+void
+dumpOperator_s(op) Operator op;
+{
+	printf("Op: %s(%d)=%d\n", op->name, op->arity, op->num);
+}
+
+void
+dumpOperator(op, full) Operator op; int full;
+{
+	dumpOperator_s(op);
+	if (full) {
+		dumpTable(op->table, 0);
+	}
+}
+
+void
+dumpOperator_l(op) Operator op;
+{
+	dumpOperator(op, 1);
+}
+
diff --git a/llvm/utils/Burg/pattern.c b/llvm/utils/Burg/pattern.c
new file mode 100644
index 00000000000..472aca579d0
--- /dev/null
+++ b/llvm/utils/Burg/pattern.c
@@ -0,0 +1,38 @@
+char rcsid_pattern[] = "$Id$";
+
+#include <stdio.h>
+#include "b.h"
+
+Pattern
+newPattern(op) Operator op;
+{
+	Pattern p;
+
+	p = (Pattern) zalloc(sizeof(struct pattern));
+	p->op = op;
+	return p;
+}
+
+void
+dumpPattern(p) Pattern p;
+{
+	int i;
+
+	if (!p) {
+		printf("[no-pattern]");
+		return;
+	}
+
+	if (p->op) {
+		printf("%s", p->op->name);
+		if (p->op->arity > 0) {
+			printf("(");
+			for (i = 0; i < p->op->arity; i++) {
+				printf("%s ", p->children[i]->name);
+			}
+			printf(")");
+		}
+	} else {
+		printf("%s", p->children[0]->name);
+	}
+}
diff --git a/llvm/utils/Burg/plank.c b/llvm/utils/Burg/plank.c
new file mode 100644
index 00000000000..1ce006dd019
--- /dev/null
+++ b/llvm/utils/Burg/plank.c
@@ -0,0 +1,921 @@
+char rcsid_plank[] = "$Id$";
+
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+#include "b.h"
+#include "fe.h"
+
+#define ERROR_VAL 0
+
+int speedflag = 0;
+
+Item_Set *sortedStates;
+static struct stateMapTable smt;
+int exceptionTolerance = 0;
+static int plankSize = 32;
+
+static Plank newPlank ARGS((void));
+static PlankMap newPlankMap ARGS((int));
+static StateMap newStateMap ARGS((void));
+static Exception newException ARGS((int, int));
+static void enterStateMap ARGS((PlankMap, short *, int, int *));
+static List assemblePlanks ARGS((void));
+static void assignRules ARGS((RuleAST));
+static int stateCompare ARGS((Item_Set *, Item_Set *));
+static int ruleCompare ARGS((RuleAST *, RuleAST *));
+static void renumber ARGS((void));
+static short * newVector ARGS((void));
+static int width ARGS((int));
+static PlankMap mapToPmap ARGS((Dimension));
+static void doDimPmaps ARGS((Operator));
+static void doNonTermPmaps ARGS((NonTerminal));
+static void makePmaps ARGS((void));
+static void outPlank ARGS((Plank));
+static void purgePlanks ARGS((List));
+static void inToEx ARGS((void));
+static void makePlankRuleMacros ARGS((void));
+static void makePlankRule ARGS((void));
+static void exceptionSwitch ARGS((List, const char *, const char *, const char *, int, const char *));
+static void doPlankLabel ARGS((Operator));
+static void doPlankLabelSafely ARGS((Operator));
+static void doPlankLabelMacrosSafely ARGS((Operator));
+static void makePlankState ARGS((void));
+
+static Plank
+newPlank()
+{
+	Plank p;
+	char buf[50];
+	static int num = 0;
+
+	p = (Plank) zalloc(sizeof(struct plank));
+	sprintf(buf, "%s_plank_%d", prefix, num++);
+	p->name = (char *) zalloc(strlen(buf)+1);
+	strcpy(p->name, buf);
+	return p;
+}
+
+static PlankMap
+newPlankMap(offset) int offset;
+{
+	PlankMap im;
+
+	im = (PlankMap) zalloc(sizeof(struct plankMap));
+	im->offset = offset;
+	return im;
+}
+
+static StateMap
+newStateMap()
+{
+	char buf[50];
+	static int num = 0;
+
+	StateMap sm;
+
+	sm = (StateMap) zalloc(sizeof(struct stateMap));
+	sprintf(buf, "f%d", num++);
+	sm->fieldname = (char *) zalloc(strlen(buf)+1);
+	strcpy(sm->fieldname, buf);
+	return sm;
+}
+
+static Exception
+newException(index, value) int index; int value;
+{
+	Exception e;
+
+	e = (Exception) zalloc(sizeof(struct except));
+	e->index = index;
+	e->value = value;
+	return e;
+}
+
+static void
+enterStateMap(im, v, width, new) PlankMap im; short * v; int width; int *new;
+{
+	int i;
+	StateMap sm;
+	List l;
+	int size;
+
+	assert(im);
+	assert(v);
+	assert(width > 0);
+	size = globalMap->count;
+
+	for (l = smt.maps; l; l = l->next) {
+		int ecount;
+
+		sm = (StateMap) l->x;
+		ecount = 0;
+		for (i = 0; i < size; i++) {
+			if (v[i] != -1 && sm->value[i] != -1 && v[i] != sm->value[i]) {
+				if (++ecount > exceptionTolerance) {
+					goto again;
+				}
+			}
+		}
+		for (i = 0; i < size; i++) {
+			assert(v[i] >= 0);
+			assert(sm->value[i] >= 0);
+			if (v[i] == -1) {
+				continue;
+			}
+			if (sm->value[i] == -1) {
+				sm->value[i] = v[i];
+			} else if (v[i] != sm->value[i]) {
+				im->exceptions = newList(newException(i,v[i]), im->exceptions);
+			}
+		}
+		im->values = sm;
+		if (width > sm->width) {
+			sm->width = width;
+		}
+		*new = 0;
+		return;
+	again: ;
+	}
+	sm = newStateMap();
+	im->values = sm;
+	sm->value = v;
+	sm->width = width;
+	*new = 1;
+	smt.maps = newList(sm, smt.maps);
+}
+
+static List
+assemblePlanks()
+{
+	List planks = 0;
+	Plank pl;
+	List p;
+	List s;
+
+	for (s = smt.maps; s; s = s->next) {
+		StateMap sm = (StateMap) s->x;
+		for (p = planks; p; p = p->next) {
+			pl = (Plank) p->x;
+			if (sm->width <= plankSize - pl->width) {
+				pl->width += sm->width;
+				pl->fields = newList(sm, pl->fields);
+				sm->plank = pl;
+				goto next;
+			}
+		}
+		pl = newPlank();
+		pl->width = sm->width;
+		pl->fields = newList(sm, 0);
+		sm->plank = pl;
+		planks = appendList(pl, planks);
+	next: ;
+	}
+	return planks;
+}
+
+RuleAST *sortedRules;
+
+static int count;
+
+static void
+assignRules(ast) RuleAST ast;
+{
+	sortedRules[count++] = ast;
+}
+
+static int
+stateCompare(s, t) Item_Set *s; Item_Set *t;
+{
+	return strcmp((*s)->op->name, (*t)->op->name);
+}
+
+static int
+ruleCompare(s, t) RuleAST *s; RuleAST *t;
+{
+	return strcmp((*s)->lhs, (*t)->lhs);
+}
+
+void
+dumpSortedStates()
+{
+	int i;
+	
+	printf("dump Sorted States: ");
+	for (i = 0; i < globalMap->count; i++) {
+		printf("%d ", sortedStates[i]->num);
+	}
+	printf("\n");
+}
+
+void
+dumpSortedRules()
+{
+	int i;
+	
+	printf("dump Sorted Rules: ");
+	for (i = 0; i < max_ruleAST; i++) {
+		printf("%d ", sortedRules[i]->rule->erulenum);
+	}
+	printf("\n");
+}
+
+static void
+renumber()
+{
+	int i;
+	Operator previousOp;
+	NonTerminal previousLHS;
+	int base_counter;
+
+	sortedStates = (Item_Set*) zalloc(globalMap->count * sizeof(Item_Set));
+	for (i = 1; i < globalMap->count; i++) {
+		sortedStates[i-1] = globalMap->set[i];
+	}
+	qsort(sortedStates, globalMap->count-1, sizeof(Item_Set), (int(*)(const void *, const void *))stateCompare);
+	previousOp = 0;
+	for (i = 0; i < globalMap->count-1; i++) {
+		sortedStates[i]->newNum = i;
+		sortedStates[i]->op->stateCount++;
+		if (previousOp != sortedStates[i]->op) {
+			sortedStates[i]->op->baseNum = i;
+			previousOp = sortedStates[i]->op;
+		}
+	}
+
+	sortedRules = (RuleAST*) zalloc(max_ruleAST * sizeof(RuleAST));
+	count = 0;
+	foreachList((ListFn) assignRules, ruleASTs);
+	qsort(sortedRules, max_ruleAST, sizeof(RuleAST), (int(*)(const void *, const void *))ruleCompare);
+	previousLHS = 0;
+	base_counter = 0;
+	for (i = 0; i < max_ruleAST; i++) {
+		if (previousLHS != sortedRules[i]->rule->lhs) {
+			sortedRules[i]->rule->lhs->baseNum = base_counter;
+			previousLHS = sortedRules[i]->rule->lhs;
+			base_counter++; /* make space for 0 */
+		}
+		sortedRules[i]->rule->newNum = base_counter;
+		sortedRules[i]->rule->lhs->ruleCount++;
+		sortedRules[i]->rule->lhs->sampleRule = sortedRules[i]->rule; /* kludge for diagnostics */
+		base_counter++;
+	}
+}
+
+static short *
+newVector()
+{
+	short *p;
+	p = (short *) zalloc(globalMap->count* sizeof(short));
+	return p;
+}
+
+static int
+width(v) int v;
+{
+	int c;
+
+	for (c = 0; v; v >>= 1) {
+		c++;
+	}
+	return c;
+
+}
+
+static PlankMap
+mapToPmap(d) Dimension d;
+{
+	PlankMap im;
+	short *v;
+	int i;
+	int new;
+
+	if (d->map->count == 1) {
+		return 0;
+	}
+	assert(d->map->count > 1);
+	im = newPlankMap(0);
+	v = newVector();
+	for (i = 0; i < globalMap->count-1; i++) {
+		int index = d->map->set[d->index_map.class[sortedStates[i]->num]->num]->num;
+		assert(index >= 0);
+		v[i+1] = index;
+	}
+	v[0] = 0;
+	enterStateMap(im, v, width(d->map->count), &new);
+	if (!new) {
+		zfree(v);
+	}
+	return im;
+}
+
+static void
+doDimPmaps(op) Operator op;
+{
+	int i, j;
+	Dimension d;
+	short *v;
+	PlankMap im;
+	int new;
+
+	if (!op->table->rules) {
+		return;
+	}
+	switch (op->arity) {
+	case 0:
+		break;
+	case 1:
+		d = op->table->dimen[0];
+		if (d->map->count > 1) {
+			v = newVector();
+			im = newPlankMap(op->baseNum);
+			for (i = 0; i < globalMap->count-1; i++) {
+				int index = d->map->set[d->index_map.class[sortedStates[i]->num]->num]->num;
+				if (index) {
+					Item_Set *ts = transLval(op->table, index, 0);
+					v[i+1] = (*ts)->newNum - op->baseNum+1;
+					assert(v[i+1] >= 0);
+				}
+			}
+			enterStateMap(im, v, width(d->map->count-1), &new);
+			if (!new) {
+				zfree(v);
+			}
+			d->pmap = im;
+		}
+		break;
+	case 2:
+		if (op->table->dimen[0]->map->count == 1 && op->table->dimen[1]->map->count == 1) {
+			op->table->dimen[0]->pmap = 0;
+			op->table->dimen[1]->pmap = 0;
+		} else if (op->table->dimen[0]->map->count == 1) {
+			v = newVector();
+			im = newPlankMap(op->baseNum);
+			d = op->table->dimen[1];
+			for (i = 0; i < globalMap->count-1; i++) {
+				int index = d->map->set[d->index_map.class[sortedStates[i]->num]->num]->num;
+				if (index) {
+					Item_Set *ts = transLval(op->table, 1, index);
+					v[i+1] = (*ts)->newNum - op->baseNum+1;
+					assert(v[i+1] >= 0);
+				}
+			}
+			enterStateMap(im, v, width(d->map->count-1), &new);
+			if (!new) {
+				zfree(v);
+			}
+			d->pmap = im;
+		} else if (op->table->dimen[1]->map->count == 1) {
+			v = newVector();
+			im = newPlankMap(op->baseNum);
+			d = op->table->dimen[0];
+			for (i = 0; i < globalMap->count-1; i++) {
+				int index = d->map->set[d->index_map.class[sortedStates[i]->num]->num]->num;
+				if (index) {
+					Item_Set *ts = transLval(op->table, index, 1);
+					v[i +1] = (*ts)->newNum - op->baseNum +1;
+					assert(v[i +1] >= 0);
+				}
+			}
+			enterStateMap(im, v, width(d->map->count-1), &new);
+			if (!new) {
+				zfree(v);
+			}
+			d->pmap = im;
+		} else {
+			op->table->dimen[0]->pmap = mapToPmap(op->table->dimen[0]);
+			op->table->dimen[1]->pmap = mapToPmap(op->table->dimen[1]);
+			/* output table */
+			fprintf(outfile, "static unsigned %s %s_%s_transition[%d][%d] = {", 
+				op->stateCount <= 255 ? "char" : "short",
+				prefix,
+				op->name,
+				op->table->dimen[0]->map->count,
+				op->table->dimen[1]->map->count);
+			for (i = 0; i < op->table->dimen[0]->map->count; i++) {
+				if (i > 0) {
+					fprintf(outfile, ",");
+				}
+				fprintf(outfile, "\n{");
+				for (j = 0; j < op->table->dimen[1]->map->count; j++) {
+					Item_Set *ts = transLval(op->table, i, j);
+					short diff;
+					if (j > 0) {
+						fprintf(outfile, ",");
+						if (j % 10 == 0) {
+							fprintf(outfile, "\t/* row %d, cols %d-%d*/\n",
+								i,
+								j-10,
+								j-1);
+						}
+					}
+					if ((*ts)->num > 0) {
+						diff = (*ts)->newNum - op->baseNum +1;
+					} else {
+						diff = 0;
+					}
+					fprintf(outfile, "%5d", diff);
+				}
+				fprintf(outfile, "}\t/* row %d */", i);
+			}
+			fprintf(outfile, "\n};\n");
+		}
+		break;
+	default:
+		assert(0);
+	}
+}
+
+static NonTerminal *ntVector;
+
+static void
+doNonTermPmaps(n) NonTerminal n;
+{
+	short *v;
+	PlankMap im;
+	int new;
+	int i;
+
+	ntVector[n->num] = n;
+	if (n->num >= last_user_nonterminal) {
+		return;
+	}
+	if (n->ruleCount <= 0) {
+		return;
+	}
+	im = newPlankMap(n->baseNum);
+	v = newVector();
+	for (i = 0; i < globalMap->count-1; i++) {
+		Rule r = globalMap->set[sortedStates[i]->num]->closed[n->num].rule;
+		if (r) {
+			r->used = 1;
+			v[i+1] = r->newNum - n->baseNum /*safely*/;
+			assert(v[i+1] >= 0);
+		}
+	}
+	enterStateMap(im, v, width(n->ruleCount+1), &new);
+	if (!new) {
+		zfree(v);
+	}
+	n->pmap = im;
+}
+
+static void
+makePmaps()
+{
+	foreachList((ListFn) doDimPmaps, operators);
+	ntVector = (NonTerminal*) zalloc((max_nonterminal) * sizeof(NonTerminal));
+	foreachList((ListFn) doNonTermPmaps, nonterminals);
+}
+
+static void
+outPlank(p) Plank p;
+{
+	List f;
+	int i;
+
+	fprintf(outfile, "static struct {\n");
+
+	for (f = p->fields; f; f = f->next) {
+		StateMap sm = (StateMap) f->x;
+		fprintf(outfile, "\tunsigned int %s:%d;\n", sm->fieldname, sm->width);
+	}
+
+	fprintf(outfile, "} %s[] = {\n", p->name);
+
+	for (i = 0; i < globalMap->count; i++) {
+		fprintf(outfile, "\t{");
+		for (f = p->fields; f; f = f->next) {
+			StateMap sm = (StateMap) f->x;
+			fprintf(outfile, "%4d,", sm->value[i] == -1 ? ERROR_VAL : sm->value[i]);
+		}
+		fprintf(outfile, "},\t/* row %d */\n", i);
+	}
+
+	fprintf(outfile, "};\n");
+}
+
+static void
+purgePlanks(planks) List planks;
+{
+	List p;
+
+	for (p = planks; p; p = p->next) {
+		Plank x = (Plank) p->x;
+		outPlank(x);
+	}
+}
+
+static void
+inToEx()
+{
+	int i;
+	int counter;
+
+	fprintf(outfile, "static short %s_eruleMap[] = {\n", prefix);
+	counter = 0;
+	for (i = 0; i < max_ruleAST; i++) {
+		if (counter > 0) {
+			fprintf(outfile, ",");
+			if (counter % 10 == 0) {
+				fprintf(outfile, "\t/* %d-%d */\n", counter-10, counter-1);
+			}
+		}
+		if (counter < sortedRules[i]->rule->newNum) {
+			assert(counter == sortedRules[i]->rule->newNum-1);
+			fprintf(outfile, "%5d", 0);
+			counter++;
+			if (counter > 0) {
+				fprintf(outfile, ",");
+				if (counter % 10 == 0) {
+					fprintf(outfile, "\t/* %d-%d */\n", counter-10, counter-1);
+				}
+			}
+		}
+		fprintf(outfile, "%5d", sortedRules[i]->rule->erulenum);
+		counter++;
+	}
+	fprintf(outfile, "\n};\n");
+}
+
+static void
+makePlankRuleMacros()
+{
+	int i;
+
+	for (i = 1; i < last_user_nonterminal; i++) {
+		List es;
+		PlankMap im = ntVector[i]->pmap;
+		fprintf(outfile, "#define %s_%s_rule(state)\t", prefix, ntVector[i]->name);
+		if (im) {
+			fprintf(outfile, "%s_eruleMap[", prefix);
+			for (es = im->exceptions; es; es = es->next) {
+				Exception e = (Exception) es->x;
+				fprintf(outfile, "((state) == %d ? %d :", 
+						e->index, e->value);
+			}
+			fprintf(outfile, "%s[state].%s", 
+				im->values->plank->name, 
+				im->values->fieldname);
+			for (es = im->exceptions; es; es = es->next) {
+				fprintf(outfile, ")");
+			}
+			fprintf(outfile, " +%d]", im->offset);
+
+		} else {
+			/* nonterminal never appears on LHS. */
+			assert(ntVector[i] ==  start);
+			fprintf(outfile, "0");
+		}
+		fprintf(outfile, "\n");
+	}
+	fprintf(outfile, "\n");
+}
+
+static void
+makePlankRule()
+{
+	int i;
+
+	makePlankRuleMacros();
+
+	fprintf(outfile, "#ifdef __STDC__\n");
+	fprintf(outfile, "int %s_rule(int state, int goalnt) {\n", prefix);
+	fprintf(outfile, "#else\n");
+	fprintf(outfile, "int %s_rule(state, goalnt) int state; int goalnt; {\n", prefix);
+	fprintf(outfile, "#endif\n");
+
+	fprintf(outfile, 
+	"\t%s_assert(state >= 0 && state < %d, %s_PANIC(\"Bad state %%d passed to %s_rule\\n\", state));\n",
+				prefix, globalMap->count, prefix, prefix);
+	fprintf(outfile, "\tswitch(goalnt) {\n");
+
+	for (i = 1; i < last_user_nonterminal; i++) {
+		fprintf(outfile, "\tcase %d:\n", i);
+		fprintf(outfile, "\t\treturn %s_%s_rule(state);\n", prefix, ntVector[i]->name);
+	}
+	fprintf(outfile, "\tdefault:\n");
+	fprintf(outfile, "\t\t%s_PANIC(\"Unknown nonterminal %%d in %s_rule;\\n\", goalnt);\n", prefix, prefix);
+	fprintf(outfile, "\t\tabort();\n");
+	fprintf(outfile, "\t\treturn 0;\n");
+	fprintf(outfile, "\t}\n");
+	fprintf(outfile, "}\n");
+}
+
+static void
+exceptionSwitch(es, sw, pre, post, offset, def) List es; const char *sw; const char *pre; const char *post; int offset; const char *def;
+{
+	if (es) {
+		fprintf(outfile, "\t\tswitch (%s) {\n", sw);
+		for (; es; es = es->next) {
+			Exception e = (Exception) es->x;
+			fprintf(outfile, "\t\tcase %d: %s %d; %s\n", e->index, pre, e->value+offset, post);
+		}
+		if (def) {
+			fprintf(outfile, "\t\tdefault: %s;\n", def);
+		}
+		fprintf(outfile, "\t\t}\n");
+	} else {
+		if (def) {
+			fprintf(outfile, "\t\t%s;\n", def);
+		}
+	}
+}
+
+static void
+doPlankLabel(op) Operator op;
+{
+	PlankMap im0;
+	PlankMap im1;
+	char buf[100];
+
+	fprintf(outfile, "\tcase %d:\n", op->num);
+	switch (op->arity) {
+	case 0:
+		fprintf(outfile, "\t\treturn %d;\n", op->table->transition[0]->newNum);
+		break;
+	case 1:
+		im0 = op->table->dimen[0]->pmap;
+		if (im0) {
+			exceptionSwitch(im0->exceptions, "l", "return ", "", im0->offset, 0);
+			fprintf(outfile, "\t\treturn %s[l].%s + %d;\n", 
+				im0->values->plank->name, im0->values->fieldname, im0->offset);
+		} else {
+			Item_Set *ts = transLval(op->table, 1, 0);
+			if (*ts) {
+				fprintf(outfile, "\t\treturn %d;\n", (*ts)->newNum);
+			} else {
+				fprintf(outfile, "\t\treturn %d;\n", ERROR_VAL);
+			}
+		}
+		break;
+	case 2:
+		im0 = op->table->dimen[0]->pmap;
+		im1 = op->table->dimen[1]->pmap;
+		if (!im0 && !im1) {
+			Item_Set *ts = transLval(op->table, 1, 1);
+			if (*ts) {
+				fprintf(outfile, "\t\treturn %d;\n", (*ts)->newNum);
+			} else {
+				fprintf(outfile, "\t\treturn %d;\n", ERROR_VAL);
+			}
+		} else if (!im0) {
+			exceptionSwitch(im1->exceptions, "r", "return ", "", im1->offset, 0);
+			fprintf(outfile, "\t\treturn %s[r].%s + %d;\n", 
+				im1->values->plank->name, im1->values->fieldname, im1->offset);
+		} else if (!im1) {
+			exceptionSwitch(im0->exceptions, "l", "return ", "", im0->offset, 0);
+			fprintf(outfile, "\t\treturn %s[l].%s + %d;\n", 
+				im0->values->plank->name, im0->values->fieldname, im0->offset);
+		} else {
+			assert(im0->offset == 0);
+			assert(im1->offset == 0);
+			sprintf(buf, "l = %s[l].%s",
+				im0->values->plank->name, im0->values->fieldname);
+			exceptionSwitch(im0->exceptions, "l", "l =", "break;", 0, buf);
+			sprintf(buf, "r = %s[r].%s",
+				im1->values->plank->name, im1->values->fieldname);
+			exceptionSwitch(im1->exceptions, "r", "r =", "break;", 0, buf);
+
+			fprintf(outfile, "\t\treturn %s_%s_transition[l][r] + %d;\n", 
+				prefix,
+				op->name,
+				op->baseNum);
+		}
+		break;
+	default:
+		assert(0);
+	}
+}
+
+static void
+doPlankLabelMacrosSafely(op) Operator op;
+{
+	PlankMap im0;
+	PlankMap im1;
+
+	switch (op->arity) {
+	case -1:
+		fprintf(outfile, "#define %s_%s_state\t0\n", prefix, op->name);
+		break;
+	case 0:
+		fprintf(outfile, "#define %s_%s_state", prefix, op->name);
+		fprintf(outfile, "\t%d\n", op->table->transition[0]->newNum+1);
+		break;
+	case 1:
+		fprintf(outfile, "#define %s_%s_state(l)", prefix, op->name);
+		im0 = op->table->dimen[0]->pmap;
+		if (im0) {
+			if (im0->exceptions) {
+				List es = im0->exceptions;
+				assert(0);
+				fprintf(outfile, "\t\tswitch (l) {\n");
+				for (; es; es = es->next) {
+					Exception e = (Exception) es->x;
+					fprintf(outfile, "\t\tcase %d: return %d;\n", e->index, e->value ? e->value+im0->offset : 0);
+				}
+				fprintf(outfile, "\t\t}\n");
+			}
+			if (speedflag) {
+				fprintf(outfile, "\t( %s[l].%s + %d )\n",
+					im0->values->plank->name, im0->values->fieldname,
+					im0->offset);
+			} else {
+				fprintf(outfile, "\t( (%s_TEMP = %s[l].%s) ? %s_TEMP + %d : 0 )\n",
+					prefix,
+					im0->values->plank->name, im0->values->fieldname,
+					prefix,
+					im0->offset);
+			}
+		} else {
+			Item_Set *ts = transLval(op->table, 1, 0);
+			if (*ts) {
+				fprintf(outfile, "\t%d\n", (*ts)->newNum+1);
+			} else {
+				fprintf(outfile, "\t%d\n", 0);
+			}
+		}
+		break;
+	case 2:
+		fprintf(outfile, "#define %s_%s_state(l,r)", prefix, op->name);
+
+		im0 = op->table->dimen[0]->pmap;
+		im1 = op->table->dimen[1]->pmap;
+		if (!im0 && !im1) {
+			Item_Set *ts = transLval(op->table, 1, 1);
+			assert(0);
+			if (*ts) {
+				fprintf(outfile, "\t\treturn %d;\n", (*ts)->newNum+1);
+			} else {
+				fprintf(outfile, "\t\treturn %d;\n", 0);
+			}
+		} else if (!im0) {
+			assert(0);
+			if (im1->exceptions) {
+				List es = im1->exceptions;
+				fprintf(outfile, "\t\tswitch (r) {\n");
+				for (; es; es = es->next) {
+					Exception e = (Exception) es->x;
+					fprintf(outfile, "\t\tcase %d: return %d;\n", e->index, e->value ? e->value+im1->offset : 0);
+				}
+				fprintf(outfile, "\t\t}\n");
+			}
+			fprintf(outfile, "\t\tstate = %s[r].%s; offset = %d;\n", 
+				im1->values->plank->name, im1->values->fieldname, im1->offset);
+			fprintf(outfile, "\t\tbreak;\n");
+		} else if (!im1) {
+			assert(0);
+			if (im0->exceptions) {
+				List es = im0->exceptions;
+				fprintf(outfile, "\t\tswitch (l) {\n");
+				for (; es; es = es->next) {
+					Exception e = (Exception) es->x;
+					fprintf(outfile, "\t\tcase %d: return %d;\n", e->index, e->value ? e->value+im0->offset : 0);
+				}
+				fprintf(outfile, "\t\t}\n");
+			}
+			fprintf(outfile, "\t\tstate = %s[l].%s; offset = %d;\n", 
+				im0->values->plank->name, im0->values->fieldname, im0->offset);
+			fprintf(outfile, "\t\tbreak;\n");
+		} else {
+			assert(im0->offset == 0);
+			assert(im1->offset == 0);
+			/*
+			sprintf(buf, "l = %s[l].%s",
+				im0->values->plank->name, im0->values->fieldname);
+			exceptionSwitch(im0->exceptions, "l", "l =", "break;", 0, buf);
+			sprintf(buf, "r = %s[r].%s",
+				im1->values->plank->name, im1->values->fieldname);
+			exceptionSwitch(im1->exceptions, "r", "r =", "break;", 0, buf);
+
+			fprintf(outfile, "\t\tstate = %s_%s_transition[l][r]; offset = %d;\n", 
+				prefix,
+				op->name,
+				op->baseNum);
+			fprintf(outfile, "\t\tbreak;\n");
+			*/
+
+			if (speedflag) {
+				fprintf(outfile, "\t( %s_%s_transition[%s[l].%s][%s[r].%s] + %d)\n",
+					prefix,
+					op->name,
+					im0->values->plank->name, im0->values->fieldname,
+					im1->values->plank->name, im1->values->fieldname,
+					op->baseNum);
+			} else {
+				fprintf(outfile, "\t( (%s_TEMP = %s_%s_transition[%s[l].%s][%s[r].%s]) ? ",
+					prefix,
+					prefix,
+					op->name,
+					im0->values->plank->name, im0->values->fieldname,
+					im1->values->plank->name, im1->values->fieldname);
+				fprintf(outfile, "%s_TEMP + %d : 0 )\n",
+					prefix,
+					op->baseNum);
+			}
+		}
+		break;
+	default:
+		assert(0);
+	}
+}
+static void
+doPlankLabelSafely(op) Operator op;
+{
+	fprintf(outfile, "\tcase %d:\n", op->num);
+	switch (op->arity) {
+	case -1:
+		fprintf(outfile, "\t\treturn 0;\n");
+		break;
+	case 0:
+		fprintf(outfile, "\t\treturn %s_%s_state;\n", prefix, op->name);
+		break;
+	case 1:
+		fprintf(outfile, "\t\treturn %s_%s_state(l);\n", prefix, op->name);
+		break;
+	case 2:
+		fprintf(outfile, "\t\treturn %s_%s_state(l,r);\n", prefix, op->name);
+		break;
+	default:
+		assert(0);
+	}
+}
+
+static void
+makePlankState()
+{
+	fprintf(outfile, "\n");
+	fprintf(outfile, "int %s_TEMP;\n", prefix);
+	foreachList((ListFn) doPlankLabelMacrosSafely, operators);
+	fprintf(outfile, "\n");
+
+	fprintf(outfile, "#ifdef __STDC__\n");
+	switch (max_arity) {
+	case -1:
+		fprintf(stderr, "ERROR: no terminals in grammar.\n");
+		exit(1);
+	case 0:
+		fprintf(outfile, "int %s_state(int op) {\n", prefix);
+		fprintf(outfile, "#else\n");
+		fprintf(outfile, "int %s_state(op) int op; {\n", prefix);
+		break;
+	case 1:
+		fprintf(outfile, "int %s_state(int op, int l) {\n", prefix);
+		fprintf(outfile, "#else\n");
+		fprintf(outfile, "int %s_state(op, l) int op; int l; {\n", prefix);
+		break;
+	case 2:
+		fprintf(outfile, "int %s_state(int op, int l, int r) {\n", prefix);
+		fprintf(outfile, "#else\n");
+		fprintf(outfile, "int %s_state(op, l, r) int op; int l; int r; {\n", prefix);
+		break;
+	default:
+		assert(0);
+	}
+	fprintf(outfile, "#endif\n");
+
+	fprintf(outfile, "\tregister int %s_TEMP;\n", prefix);
+
+	fprintf(outfile, "#ifndef NDEBUG\n");
+
+	fprintf(outfile, "\tswitch (op) {\n");
+	opsOfArity(2);
+	if (max_arity >= 2) {
+		fprintf(outfile, 
+		"\t\t%s_assert(r >= 0 && r < %d, %s_PANIC(\"Bad state %%d passed to %s_state\\n\", r));\n",
+				prefix, globalMap->count, prefix, prefix);
+		fprintf(outfile, "\t\t/*FALLTHROUGH*/\n");
+	}
+	opsOfArity(1);
+	if (max_arity > 1) {
+		fprintf(outfile, 
+		"\t\t%s_assert(l >= 0 && l < %d, %s_PANIC(\"Bad state %%d passed to %s_state\\n\", l));\n",
+				prefix, globalMap->count, prefix, prefix);
+		fprintf(outfile, "\t\t/*FALLTHROUGH*/\n");
+	}
+	opsOfArity(0);
+	fprintf(outfile, "\t\tbreak;\n");
+	fprintf(outfile, "\t}\n");
+	fprintf(outfile, "#endif\n");
+
+	fprintf(outfile, "\tswitch (op) {\n");
+	fprintf(outfile,"\tdefault: %s_PANIC(\"Unknown op %%d in %s_state\\n\", op); abort(); return 0;\n",
+		prefix, prefix);
+	foreachList((ListFn) doPlankLabelSafely, operators);
+	fprintf(outfile, "\t}\n");
+
+	fprintf(outfile, "}\n");
+}
+
+void
+makePlanks()
+{
+	List planks;
+	renumber();
+	makePmaps();
+	planks = assemblePlanks();
+	purgePlanks(planks);
+	inToEx();
+	makePlankRule();
+	makePlankState();
+}
diff --git a/llvm/utils/Burg/queue.c b/llvm/utils/Burg/queue.c
new file mode 100644
index 00000000000..76e5ea9b57b
--- /dev/null
+++ b/llvm/utils/Burg/queue.c
@@ -0,0 +1,64 @@
+char rcsid_queue[] = "$Id$";
+
+#include "b.h"
+#include <stdio.h>
+
+Queue globalQ;
+
+Queue
+newQ()
+{
+	Queue q;
+
+	q = (Queue) zalloc(sizeof(struct queue));
+	assert(q);
+	q->head = 0;
+	q->tail = 0;
+
+	return q;
+}
+
+void
+addQ(q, ts) Queue q; Item_Set ts;
+{
+	List qe;
+
+	assert(q);
+	assert(ts);
+
+	qe = newList(ts, 0);
+	if (q->head) {
+		assert(q->tail);
+		q->tail->next = qe;
+		q->tail = qe;
+	} else {
+		q->head = q->tail = qe;
+	}
+}
+
+Item_Set
+popQ(q) Queue q;
+{
+	List qe;
+	Item_Set ts;
+
+	assert(q);
+
+	if (q->head) {
+		qe = q->head;
+		q->head = q->head->next;
+		ts = (Item_Set) qe->x;
+		zfree(qe);
+		return ts;
+	} else {
+		return 0;
+	}
+}
+
+void
+dumpQ(q) Queue q;
+{
+	printf("Begin Queue\n");
+	foreachList((ListFn)dumpItem_Set, q->head);
+	printf("End Queue\n");
+}
diff --git a/llvm/utils/Burg/rule.c b/llvm/utils/Burg/rule.c
new file mode 100644
index 00000000000..ee5c89e8933
--- /dev/null
+++ b/llvm/utils/Burg/rule.c
@@ -0,0 +1,49 @@
+char rcsid_rule[] = "$Id$";
+
+#include "b.h"
+#include <stdio.h>
+
+RuleNum max_rule;
+int max_erule_num;
+
+struct rule stub_rule;
+
+List rules;
+
+Rule
+newRule(delta, erulenum, lhs, pat) DeltaPtr delta; ERuleNum erulenum; NonTerminal lhs; Pattern pat;
+{
+	Rule p;
+
+	p = (Rule) zalloc(sizeof(struct rule));
+	assert(p);
+	ASSIGNCOST(p->delta, delta);
+	p->erulenum = erulenum;
+	if (erulenum > max_erule_num) {
+		max_erule_num = erulenum;
+	}
+	p->num = max_rule++;
+	p->lhs = lhs;
+	p->pat = pat;
+
+	rules = newList(p, rules);
+
+	return p;
+}
+
+void
+dumpRule(p) Rule p;
+{
+	dumpNonTerminal(p->lhs);
+	printf(" : ");
+	dumpPattern(p->pat);
+	printf(" ");
+	dumpCost(p->delta);
+	printf("\n");
+}
+
+void
+dumpRuleList(l) List l;
+{
+	foreachList((ListFn)dumpRule, l);
+}
diff --git a/llvm/utils/Burg/sample.gr b/llvm/utils/Burg/sample.gr
new file mode 100644
index 00000000000..e1f7283b6d6
--- /dev/null
+++ b/llvm/utils/Burg/sample.gr
@@ -0,0 +1,150 @@
+%{
+#include <stdio.h>
+
+typedef struct node *NODEPTR_TYPE;
+
+struct node {
+	int op, state_label;
+	NODEPTR_TYPE left, right;
+};
+
+#define OP_LABEL(p)	((p)->op)
+#define STATE_LABEL(p)	((p)->state_label)
+#define LEFT_CHILD(p)	((p)->left)
+#define RIGHT_CHILD(p)	((p)->right)
+#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);
+
+%%
+
+#define Assign 1
+#define Constant 2
+#define Fetch 3
+#define Four 4
+#define Mul 5
+#define Plus 6
+
+#ifdef __STDC__
+#define ARGS(x) x
+#else
+#define ARGS(x) ()
+#endif
+
+NODEPTR_TYPE buildtree ARGS((int, NODEPTR_TYPE, NODEPTR_TYPE));
+void printcover ARGS((NODEPTR_TYPE, int, int));
+void printtree ARGS((NODEPTR_TYPE));
+int treecost ARGS((NODEPTR_TYPE, int, int));
+void printMatches ARGS((NODEPTR_TYPE));
+int main ARGS((void));
+
+NODEPTR_TYPE buildtree(op, left, right) int op; NODEPTR_TYPE left; NODEPTR_TYPE right; {
+	NODEPTR_TYPE p;
+	extern void *malloc ARGS((unsigned));
+
+	p = (NODEPTR_TYPE) malloc(sizeof *p);
+	p->op = op;
+	p->left = left;
+	p->right = right;
+	return p;
+}
+
+void printcover(p, goalnt, indent) NODEPTR_TYPE p; int goalnt; int indent; {
+	int eruleno = burm_rule(STATE_LABEL(p), goalnt);
+	short *nts = burm_nts[eruleno];
+	NODEPTR_TYPE kids[10];
+	int i;
+	
+	if (eruleno == 0) {
+		printf("no cover\n");
+		return;
+	}
+	for (i = 0; i < indent; i++)
+		printf(".");
+	printf("%s\n", burm_string[eruleno]);
+	burm_kids(p, eruleno, kids);
+	for (i = 0; nts[i]; i++)
+		printcover(kids[i], nts[i], indent+1);
+}
+
+void printtree(p) NODEPTR_TYPE p; {
+	int op = burm_op_label(p);
+
+	printf("%s", burm_opname[op]);
+	switch (burm_arity[op]) {
+	case 0:
+		break;
+	case 1:
+		printf("(");
+		printtree(burm_child(p, 0));
+		printf(")");
+		break;
+	case 2:
+		printf("(");
+		printtree(burm_child(p, 0));
+		printf(", ");
+		printtree(burm_child(p, 1));
+		printf(")");
+		break;
+	}
+}
+
+int treecost(p, goalnt, costindex) NODEPTR_TYPE p; int goalnt; int costindex; {
+	int eruleno = burm_rule(STATE_LABEL(p), goalnt);
+	int cost = burm_cost[eruleno][costindex], i;
+	short *nts = burm_nts[eruleno];
+	NODEPTR_TYPE kids[10];
+
+	burm_kids(p, eruleno, kids);
+	for (i = 0; nts[i]; i++)
+		cost += treecost(kids[i], nts[i], costindex);
+	return cost;
+}
+
+void printMatches(p) NODEPTR_TYPE p; {
+	int nt;
+	int eruleno;
+
+	printf("Node 0x%lx= ", (unsigned long)p);
+	printtree(p);
+	printf(" matched rules:\n");
+	for (nt = 1; burm_ntname[nt] != (char*)NULL; nt++)
+		if ((eruleno = burm_rule(STATE_LABEL(p), nt)) != 0)
+			printf("\t%s\n", burm_string[eruleno]);
+}
+
+main() {
+	NODEPTR_TYPE p;
+
+	p = buildtree(Assign,
+		buildtree(Constant, 0, 0),
+		buildtree(Fetch,
+			buildtree(Plus,
+				buildtree(Constant, 0, 0),
+				buildtree(Mul,
+					buildtree(Four, 0, 0),
+					buildtree(Fetch, buildtree(Constant, 0, 0), 0)
+				)
+			),
+			0
+		)
+	);
+	printtree(p);
+	printf("\n\n");
+	burm_label(p);
+	printcover(p, 1, 0);
+	printf("\nCover cost == %d\n\n", treecost(p, 1, 0));
+	printMatches(p);
+	return 0;
+}
+
diff --git a/llvm/utils/Burg/string.c b/llvm/utils/Burg/string.c
new file mode 100644
index 00000000000..9b69c3045ff
--- /dev/null
+++ b/llvm/utils/Burg/string.c
@@ -0,0 +1,65 @@
+char rcsid_string[] = "$Id$";
+
+#include <stdio.h>
+#include <string.h>
+#include "b.h"
+#include "fe.h"
+
+static StrTableElement newStrTableElement ARGS((void));
+
+StrTable
+newStrTable()
+{
+	return (StrTable) zalloc(sizeof(struct strTable));
+}
+
+static StrTableElement
+newStrTableElement()
+{
+	return (StrTableElement) zalloc(sizeof(struct strTableElement));
+}
+
+void
+dumpStrTable(t) StrTable t;
+{ 
+	List e;
+	IntList r;
+
+	printf("Begin StrTable\n");
+	for (e = t->elems; e; e = e->next) {
+		StrTableElement el = (StrTableElement) e->x;
+		printf("%s: ", el->str);
+		for (r = el->erulenos; r; r = r->next) {
+			int i = r->x;
+			printf("(%d)", i);
+		}
+		printf("\n");
+	}
+	printf("End StrTable\n");
+}
+
+StrTableElement
+addString(t, s, eruleno, new) StrTable t; char *s; int eruleno; int *new;
+{
+	List l;
+	StrTableElement ste;
+
+	assert(t);
+	for (l = t->elems; l; l = l->next) {
+		StrTableElement e = (StrTableElement) l->x;
+
+		assert(e);
+		if (!strcmp(s, e->str)) {
+			e->erulenos = newIntList(eruleno, e->erulenos);
+			*new = 0;
+			return e;
+		}
+	}
+	ste = newStrTableElement();
+	ste->erulenos = newIntList(eruleno, 0);
+	ste->str = (char *) zalloc(strlen(s) + 1);
+	strcpy(ste->str, s);
+	t->elems = newList(ste, t->elems);
+	*new = 1;
+	return ste;
+}
diff --git a/llvm/utils/Burg/symtab.c b/llvm/utils/Burg/symtab.c
new file mode 100644
index 00000000000..3ecab2fc5ff
--- /dev/null
+++ b/llvm/utils/Burg/symtab.c
@@ -0,0 +1,38 @@
+char rcsid_symtab[] = "$Id$";
+
+#include <stdio.h>
+#include <string.h>
+#include "b.h"
+#include "fe.h"
+
+static List symtab;
+
+Symbol
+newSymbol(name) char *name;
+{
+	Symbol s;
+
+	s = (Symbol) zalloc(sizeof(struct symbol));
+	assert(s);
+	s->name = name;
+	return s;
+}
+
+Symbol
+enter(name, new) char *name; int *new;
+{
+	List l;
+	Symbol s;
+
+	*new = 0;
+	for (l = symtab; l; l = l->next) {
+		s = (Symbol) l->x;
+		if (!strcmp(name, s->name)) {
+			return s;
+		}
+	}
+	*new = 1;
+	s = newSymbol(name);
+	symtab = newList(s, symtab);
+	return s;
+}
diff --git a/llvm/utils/Burg/table.c b/llvm/utils/Burg/table.c
new file mode 100644
index 00000000000..1de74f9a107
--- /dev/null
+++ b/llvm/utils/Burg/table.c
@@ -0,0 +1,552 @@
+char rcsid_table[] = "$Id$";
+
+#include "b.h"
+#include <string.h>
+#include <stdio.h>
+
+static void growIndex_Map ARGS((Index_Map *));
+static Relevant newRelevant ARGS((void));
+static Dimension newDimension ARGS((Operator, int));
+static void GT_1 ARGS((Table));
+static void GT_2_0 ARGS((Table));
+static void GT_2_1 ARGS((Table));
+static void growTransition ARGS((Table, int));
+static Item_Set restrict ARGS((Dimension, Item_Set));
+static void addHP_1 ARGS((Table, Item_Set));
+static void addHP_2_0 ARGS((Table, Item_Set));
+static void addHP_2_1 ARGS((Table, Item_Set));
+static void addHyperPlane ARGS((Table, int, Item_Set));
+
+static void
+growIndex_Map(r) Index_Map *r;
+{
+	Index_Map new;
+
+	new.max_size = r->max_size + STATES_INCR;
+	new.class = (Item_Set*) zalloc(new.max_size * sizeof(Item_Set));
+	assert(new.class);
+	memcpy(new.class, r->class, r->max_size * sizeof(Item_Set));
+	zfree(r->class);
+	*r = new;
+}
+
+static Relevant
+newRelevant()
+{
+	Relevant r = (Relevant) zalloc(max_nonterminal * sizeof(*r));
+	return r;
+}
+
+void
+addRelevant(r, nt) Relevant r; NonTerminalNum nt;
+{
+	int i;
+
+	for (i = 0; r[i]; i++) {
+		if (r[i] == nt) {
+			break;
+		}
+	}
+	if (!r[i]) {
+		r[i] = nt;
+	}
+}
+
+static Dimension
+newDimension(op, index) Operator op; ArityNum index;
+{
+	Dimension d;
+	List pl;
+	Relevant r;
+
+	assert(op);
+	assert(index >= 0 && index < op->arity);
+	d = (Dimension) zalloc(sizeof(struct dimension));
+	assert(d);
+
+	r = d->relevant = newRelevant();
+	for (pl = rules; pl; pl = pl->next) {
+		Rule pr = (Rule) pl->x;
+		if (pr->pat->op == op) {
+			addRelevant(r, pr->pat->children[index]->num);
+		}
+	}
+
+	d->index_map.max_size = STATES_INCR;
+	d->index_map.class = (Item_Set*) 
+			zalloc(d->index_map.max_size * sizeof(Item_Set));
+	d->map = newMapping(DIM_MAP_SIZE);
+	d->max_size = TABLE_INCR;
+
+	return d;
+}
+
+Table
+newTable(op) Operator op;
+{
+	Table t;
+	int i, size;
+
+	assert(op);
+
+	t = (Table) zalloc(sizeof(struct table));
+	assert(t);
+
+	t->op = op;
+
+	for (i = 0; i < op->arity; i++) {
+		t->dimen[i] = newDimension(op, i);
+	}
+
+	size = 1;
+	for (i = 0; i < op->arity; i++) {
+		size *= t->dimen[i]->max_size;
+	}
+	t->transition = (Item_Set*) zalloc(size * sizeof(Item_Set));
+	t->relevant = newRelevant();
+	assert(t->transition);
+
+	return t;
+}
+
+static void
+GT_1(t) Table t;
+{
+	Item_Set	*ts;
+	ItemSetNum 	oldsize = t->dimen[0]->max_size;
+	ItemSetNum 	newsize = t->dimen[0]->max_size + TABLE_INCR;
+
+	t->dimen[0]->max_size = newsize;
+
+	ts = (Item_Set*) zalloc(newsize * sizeof(Item_Set));
+	assert(ts);
+	memcpy(ts, t->transition, oldsize * sizeof(Item_Set));
+	zfree(t->transition);
+	t->transition = ts;
+}
+
+static void
+GT_2_0(t) Table t;
+{
+	Item_Set	*ts;
+	ItemSetNum 	oldsize = t->dimen[0]->max_size;
+	ItemSetNum 	newsize = t->dimen[0]->max_size + TABLE_INCR;
+	int		size;
+
+	t->dimen[0]->max_size = newsize;
+
+	size = newsize * t->dimen[1]->max_size;
+
+	ts = (Item_Set*) zalloc(size * sizeof(Item_Set));
+	assert(ts);
+	memcpy(ts, t->transition, oldsize*t->dimen[1]->max_size * sizeof(Item_Set));
+	zfree(t->transition);
+	t->transition = ts;
+}
+
+static void
+GT_2_1(t) Table t;
+{
+	Item_Set	*ts;
+	ItemSetNum 	oldsize = t->dimen[1]->max_size;
+	ItemSetNum 	newsize = t->dimen[1]->max_size + TABLE_INCR;
+	int		size;
+	Item_Set	*from;
+	Item_Set	*to;
+	int 		i1, i2;
+
+	t->dimen[1]->max_size = newsize;
+
+	size = newsize * t->dimen[0]->max_size;
+
+	ts = (Item_Set*) zalloc(size * sizeof(Item_Set));
+	assert(ts);
+
+	from = t->transition;
+	to = ts;
+	for (i1 = 0; i1 < t->dimen[0]->max_size; i1++) {
+		for (i2 = 0; i2 < oldsize; i2++) {
+			to[i2] = from[i2];
+		}
+		to += newsize;
+		from += oldsize;
+	}
+	zfree(t->transition);
+	t->transition = ts;
+}
+
+static void
+growTransition(t, dim) Table t; ArityNum dim;
+{
+
+	assert(t);
+	assert(t->op);
+	assert(dim < t->op->arity);
+
+	switch (t->op->arity) {
+	default:
+		assert(0);
+		break;
+	case 1:
+		GT_1(t);
+		return;
+	case 2:
+		switch (dim) {
+		default:
+			assert(0);
+			break;
+		case 0:
+			GT_2_0(t);
+			return;
+		case 1:
+			GT_2_1(t);
+			return;
+		}
+	}
+}
+
+static Item_Set
+restrict(d, ts) Dimension d; Item_Set ts;
+{
+	DeltaCost	base;
+	Item_Set	r;
+	int found;
+	register Relevant r_ptr = d->relevant;
+	register Item *ts_current = ts->closed;
+	register Item *r_current;
+	register int i;
+	register int nt;
+
+	ZEROCOST(base);
+	found = 0;
+	r = newItem_Set(d->relevant);
+	r_current = r->virgin;
+	for (i = 0; (nt = r_ptr[i]) != 0; i++) {
+		if (ts_current[nt].rule) {
+			r_current[nt].rule = &stub_rule;
+			if (!found) {
+				found = 1;
+				ASSIGNCOST(base, ts_current[nt].delta);
+			} else {
+				if (LESSCOST(ts_current[nt].delta, base)) {
+					ASSIGNCOST(base, ts_current[nt].delta);
+				}
+			}
+		}
+	}
+
+	/* zero align */
+	for (i = 0; (nt = r_ptr[i]) != 0; i++) {
+		if (r_current[nt].rule) {
+			ASSIGNCOST(r_current[nt].delta, ts_current[nt].delta);
+			MINUSCOST(r_current[nt].delta, base);
+		}
+	}
+	assert(!r->closed);
+	r->representative = ts;
+	return r;
+}
+
+static void
+addHP_1(t, ts) Table t; Item_Set ts;
+{
+	List pl;
+	Item_Set e;
+	Item_Set tmp;
+	int new;
+
+	e = newItem_Set(t->relevant);
+	assert(e);
+	e->kids[0] = ts->representative;
+	for (pl = t->rules; pl; pl = pl->next) {
+		Rule p = (Rule) pl->x;
+		if (t->op == p->pat->op && ts->virgin[p->pat->children[0]->num].rule) {
+			DeltaCost dc;
+			ASSIGNCOST(dc, ts->virgin[p->pat->children[0]->num].delta);
+			ADDCOST(dc, p->delta);
+			if (!e->virgin[p->lhs->num].rule || LESSCOST(dc, e->virgin[p->lhs->num].delta)) {
+				e->virgin[p->lhs->num].rule = p;
+				ASSIGNCOST(e->virgin[p->lhs->num].delta, dc);
+				e->op = t->op;
+			}
+		}
+	}
+	trim(e);
+	zero(e);
+	tmp = encode(globalMap, e, &new);
+	assert(ts->num < t->dimen[0]->map->max_size);
+	t->transition[ts->num] = tmp;
+	if (new) {
+		closure(e);
+		addQ(globalQ, tmp);
+	} else {
+		freeItem_Set(e);
+	}
+}
+
+static void
+addHP_2_0(t, ts) Table t; Item_Set ts;
+{
+	List pl;
+	register Item_Set e;
+	Item_Set tmp;
+	int new;
+	int i2;
+
+	assert(t->dimen[1]->map->count <= t->dimen[1]->map->max_size);
+	for (i2 = 0; i2 < t->dimen[1]->map->count; i2++) {
+		e = newItem_Set(t->relevant);
+		assert(e);
+		e->kids[0] = ts->representative;
+		e->kids[1] = t->dimen[1]->map->set[i2]->representative;
+		for (pl = t->rules; pl; pl = pl->next) {
+			register Rule p = (Rule) pl->x;
+
+			if (t->op == p->pat->op 
+					&& ts->virgin[p->pat->children[0]->num].rule
+					&& t->dimen[1]->map->set[i2]->virgin[p->pat->children[1]->num].rule){
+				DeltaCost dc;
+				ASSIGNCOST(dc, p->delta);
+				ADDCOST(dc, ts->virgin[p->pat->children[0]->num].delta);
+				ADDCOST(dc, t->dimen[1]->map->set[i2]->virgin[p->pat->children[1]->num].delta);
+
+				if (!e->virgin[p->lhs->num].rule || LESSCOST(dc, e->virgin[p->lhs->num].delta)) {
+					e->virgin[p->lhs->num].rule = p;
+					ASSIGNCOST(e->virgin[p->lhs->num].delta, dc);
+					e->op = t->op;
+				}
+			}
+		}
+		trim(e);
+		zero(e);
+		tmp = encode(globalMap, e, &new);
+		assert(ts->num < t->dimen[0]->map->max_size);
+		t->transition[ts->num * t->dimen[1]->max_size + i2] = tmp;
+		if (new) {
+			closure(e);
+			addQ(globalQ, tmp);
+		} else {
+			freeItem_Set(e);
+		}
+	}
+}
+
+static void
+addHP_2_1(t, ts) Table t; Item_Set ts;
+{
+	List pl;
+	register Item_Set e;
+	Item_Set tmp;
+	int new;
+	int i1;
+
+	assert(t->dimen[0]->map->count <= t->dimen[0]->map->max_size);
+	for (i1 = 0; i1 < t->dimen[0]->map->count; i1++) {
+		e = newItem_Set(t->relevant);
+		assert(e);
+		e->kids[0] = t->dimen[0]->map->set[i1]->representative;
+		e->kids[1] = ts->representative;
+		for (pl = t->rules; pl; pl = pl->next) {
+			register Rule p = (Rule) pl->x;
+
+			if (t->op == p->pat->op 
+					&& ts->virgin[p->pat->children[1]->num].rule
+					&& t->dimen[0]->map->set[i1]->virgin[p->pat->children[0]->num].rule){
+				DeltaCost dc;
+				ASSIGNCOST(dc, p->delta );
+				ADDCOST(dc, ts->virgin[p->pat->children[1]->num].delta);
+				ADDCOST(dc, t->dimen[0]->map->set[i1]->virgin[p->pat->children[0]->num].delta);
+				if (!e->virgin[p->lhs->num].rule || LESSCOST(dc, e->virgin[p->lhs->num].delta)) {
+					e->virgin[p->lhs->num].rule = p;
+					ASSIGNCOST(e->virgin[p->lhs->num].delta, dc);
+					e->op = t->op;
+				}
+			}
+		}
+		trim(e);
+		zero(e);
+		tmp = encode(globalMap, e, &new);
+		assert(ts->num < t->dimen[1]->map->max_size);
+		t->transition[i1 * t->dimen[1]->max_size + ts->num] = tmp;
+		if (new) {
+			closure(e);
+			addQ(globalQ, tmp);
+		} else {
+			freeItem_Set(e);
+		}
+	}
+}
+
+static void
+addHyperPlane(t, i, ts) Table t; ArityNum i; Item_Set ts;
+{
+	switch (t->op->arity) {
+	default:
+		assert(0);
+		break;
+	case 1:
+		addHP_1(t, ts);
+		return;
+	case 2:
+		switch (i) {
+		default:
+			assert(0);
+			break;
+		case 0:
+			addHP_2_0(t, ts);
+			return;
+		case 1:
+			addHP_2_1(t, ts);
+			return;
+		}
+	}
+}
+
+void
+addToTable(t, ts) Table t; Item_Set ts;
+{
+	ArityNum i;
+
+	assert(t);
+	assert(ts);
+	assert(t->op);
+
+	for (i = 0; i < t->op->arity; i++) {
+		Item_Set r;
+		Item_Set tmp;
+		int new;
+
+		r = restrict(t->dimen[i], ts);
+		tmp = encode(t->dimen[i]->map, r, &new);
+		if (t->dimen[i]->index_map.max_size <= ts->num) {
+			growIndex_Map(&t->dimen[i]->index_map);
+		}
+		assert(ts->num < t->dimen[i]->index_map.max_size);
+		t->dimen[i]->index_map.class[ts->num] = tmp;
+		if (new) {
+			if (t->dimen[i]->max_size <= r->num) {
+				growTransition(t, i);
+			}
+			addHyperPlane(t, i, r);
+		} else {
+			freeItem_Set(r);
+		}
+	}
+}
+
+Item_Set *
+transLval(t, row, col) Table t; int row; int col;
+{
+	switch (t->op->arity) {
+	case 0:
+		assert(row == 0);
+		assert(col == 0);
+		return t->transition;
+	case 1:
+		assert(col == 0);
+		return t->transition + row;
+	case 2:
+		return t->transition + row * t->dimen[1]->max_size + col;
+	default:
+		assert(0);
+	}
+	return 0;
+}
+
+void
+dumpRelevant(r) Relevant r;
+{
+	for (; *r; r++) {
+		printf("%4d", *r);
+	}
+}
+
+void
+dumpIndex_Map(r) Index_Map *r;
+{
+	int i;
+
+	printf("BEGIN Index_Map: MaxSize (%d)\n", r->max_size);
+	for (i = 0; i < globalMap->count; i++) {
+		printf("\t#%d: -> %d\n", i, r->class[i]->num);
+	}
+	printf("END Index_Map:\n");
+}
+
+void
+dumpDimension(d) Dimension d;
+{
+	printf("BEGIN Dimension:\n");
+	printf("Relevant: ");
+	dumpRelevant(d->relevant);
+	printf("\n");
+	dumpIndex_Map(&d->index_map);
+	dumpMapping(d->map);
+	printf("MaxSize of dimension = %d\n", d->max_size);
+	printf("END Dimension\n");
+}
+
+void
+dumpTable(t, full) Table t; int full;
+{
+	int i;
+
+	if (!t) {
+		printf("NO Table yet.\n");
+		return;
+	}
+	printf("BEGIN Table:\n");
+	if (full) {
+		dumpOperator(t->op, 0);
+	}
+	for (i = 0; i < t->op->arity; i++) {
+		printf("BEGIN dimension(%d)\n", i);
+		dumpDimension(t->dimen[i]);
+		printf("END dimension(%d)\n", i);
+	}
+	dumpTransition(t);
+	printf("END Table:\n");
+}
+
+void
+dumpTransition(t) Table t;
+{
+	int i,j;
+
+	switch (t->op->arity) {
+	case 0:
+		printf("{ %d }", t->transition[0]->num);
+		break;
+	case 1:
+		printf("{");
+		for (i = 0; i < t->dimen[0]->map->count; i++) {
+			if (i > 0) {
+				printf(",");
+			}
+			printf("%5d", t->transition[i]->num);
+		}
+		printf("}");
+		break;
+	case 2:
+		printf("{");
+		for (i = 0; i < t->dimen[0]->map->count; i++) {
+			if (i > 0) {
+				printf(",");
+			}
+			printf("\n");
+			printf("{");
+			for (j = 0; j < t->dimen[1]->map->count; j++) {
+				Item_Set *ts = transLval(t, i, j);
+				if (j > 0) {
+					printf(",");
+				}
+				printf("%5d", (*ts)->num);
+			}
+			printf("}");
+		}
+		printf("\n}\n");
+		break;
+	default:
+		assert(0);
+	}
+}
diff --git a/llvm/utils/Burg/trim.c b/llvm/utils/Burg/trim.c
new file mode 100644
index 00000000000..05ee2d0f646
--- /dev/null
+++ b/llvm/utils/Burg/trim.c
@@ -0,0 +1,412 @@
+char rcsid_trim[] = "$Id$";
+
+#include <stdio.h>
+#include "b.h"
+#include "fe.h"
+
+Relation *allpairs;
+
+int trimflag = 0;
+int debugTrim = 0;
+
+static void siblings ARGS((int, int));
+static void findAllNexts ARGS((void));
+static Relation *newAllPairs ARGS((void));
+
+static void
+siblings(i, j) int i; int j;
+{
+	int k;
+	List pl;
+	DeltaCost Max;
+	int foundmax;
+
+	allpairs[i][j].sibComputed = 1;
+
+	if (i == 1) {
+		return; /* never trim start symbol */
+	}
+	if (i==j) {
+		return;
+	}
+
+	ZEROCOST(Max);
+	foundmax = 0;
+
+	for (k = 1; k < max_nonterminal; k++) {
+		DeltaCost tmp;
+
+		if (k==i || k==j) {
+			continue;
+		}
+		if (!allpairs[k][i].rule) {
+			continue;
+		}
+		if (!allpairs[k][j].rule) {
+			return;
+		}
+		ASSIGNCOST(tmp, allpairs[k][j].chain);
+		MINUSCOST(tmp, allpairs[k][i].chain);
+		if (foundmax) {
+			if (LESSCOST(Max, tmp)) {
+				ASSIGNCOST(Max, tmp);
+			}
+		} else {
+			foundmax = 1;
+			ASSIGNCOST(Max, tmp);
+		}
+	}
+
+	for (pl = rules; pl; pl = pl->next) {
+		Rule p = (Rule) pl->x;
+		Operator op = p->pat->op;
+		List oprule;
+		DeltaCost Min;
+		int foundmin;
+		
+		if (!op) {
+			continue;
+		}
+		switch (op->arity) {
+		case 0:
+			continue;
+		case 1:
+			if (!allpairs[p->pat->children[0]->num ][ i].rule) {
+				continue;
+			}
+			foundmin = 0;
+			for (oprule = op->table->rules; oprule; oprule = oprule->next) {
+				Rule s = (Rule) oprule->x;
+				DeltaPtr Cx;
+				DeltaPtr Csj;
+				DeltaPtr Cpi;
+				DeltaCost tmp;
+
+				if (!allpairs[p->lhs->num ][ s->lhs->num].rule
+				 || !allpairs[s->pat->children[0]->num ][ j].rule) {
+					continue;
+				}
+				Cx = allpairs[p->lhs->num ][ s->lhs->num].chain;
+				Csj= allpairs[s->pat->children[0]->num ][ j].chain;
+				Cpi= allpairs[p->pat->children[0]->num ][ i].chain;
+				ASSIGNCOST(tmp, Cx);
+				ADDCOST(tmp, s->delta);
+				ADDCOST(tmp, Csj);
+				MINUSCOST(tmp, Cpi);
+				MINUSCOST(tmp, p->delta);
+				if (foundmin) {
+					if (LESSCOST(tmp, Min)) {
+						ASSIGNCOST(Min, tmp);
+					}
+				} else {
+					foundmin = 1;
+					ASSIGNCOST(Min, tmp);
+				}
+			}
+			if (!foundmin) {
+				return;
+			}
+			if (foundmax) {
+				if (LESSCOST(Max, Min)) {
+					ASSIGNCOST(Max, Min);
+				}
+			} else {
+				foundmax = 1;
+				ASSIGNCOST(Max, Min);
+			}
+			break;
+		case 2:
+		/* do first dimension */
+		if (allpairs[p->pat->children[0]->num ][ i].rule) {
+			foundmin = 0;
+			for (oprule = op->table->rules; oprule; oprule = oprule->next) {
+				Rule s = (Rule) oprule->x;
+				DeltaPtr Cx;
+				DeltaPtr Cb;
+				DeltaPtr Csj;
+				DeltaPtr Cpi;
+				DeltaCost tmp;
+
+				if (allpairs[p->lhs->num ][ s->lhs->num].rule
+				 && allpairs[s->pat->children[0]->num ][ j].rule
+				 && allpairs[s->pat->children[1]->num ][ p->pat->children[1]->num].rule) {
+					Cx = allpairs[p->lhs->num ][ s->lhs->num].chain;
+					Csj= allpairs[s->pat->children[0]->num ][ j].chain;
+					Cpi= allpairs[p->pat->children[0]->num ][ i].chain;
+					Cb = allpairs[s->pat->children[1]->num ][ p->pat->children[1]->num].chain;
+					ASSIGNCOST(tmp, Cx);
+					ADDCOST(tmp, s->delta);
+					ADDCOST(tmp, Csj);
+					ADDCOST(tmp, Cb);
+					MINUSCOST(tmp, Cpi);
+					MINUSCOST(tmp, p->delta);
+					if (foundmin) {
+						if (LESSCOST(tmp, Min)) {
+							ASSIGNCOST(Min, tmp);
+						}
+					} else {
+						foundmin = 1;
+						ASSIGNCOST(Min, tmp);
+					}
+				}
+			}
+			if (!foundmin) {
+				return;
+			}
+			if (foundmax) {
+				if (LESSCOST(Max, Min)) {
+					ASSIGNCOST(Max, Min);
+				}
+			} else {
+				foundmax = 1;
+				ASSIGNCOST(Max, Min);
+			}
+		}
+		/* do second dimension */
+		if (allpairs[p->pat->children[1]->num ][ i].rule) {
+			foundmin = 0;
+			for (oprule = op->table->rules; oprule; oprule = oprule->next) {
+				Rule s = (Rule) oprule->x;
+				DeltaPtr Cx;
+				DeltaPtr Cb;
+				DeltaPtr Csj;
+				DeltaPtr Cpi;
+				DeltaCost tmp;
+
+				if (allpairs[p->lhs->num ][ s->lhs->num].rule
+				 && allpairs[s->pat->children[1]->num ][ j].rule
+				 && allpairs[s->pat->children[0]->num ][ p->pat->children[0]->num].rule) {
+					Cx = allpairs[p->lhs->num ][ s->lhs->num].chain;
+					Csj= allpairs[s->pat->children[1]->num ][ j].chain;
+					Cpi= allpairs[p->pat->children[1]->num ][ i].chain;
+					Cb = allpairs[s->pat->children[0]->num ][ p->pat->children[0]->num].chain;
+					ASSIGNCOST(tmp, Cx);
+					ADDCOST(tmp, s->delta);
+					ADDCOST(tmp, Csj);
+					ADDCOST(tmp, Cb);
+					MINUSCOST(tmp, Cpi);
+					MINUSCOST(tmp, p->delta);
+					if (foundmin) {
+						if (LESSCOST(tmp, Min)) {
+							ASSIGNCOST(Min, tmp);
+						}
+					} else {
+						foundmin = 1;
+						ASSIGNCOST(Min, tmp);
+					}
+				}
+			}
+			if (!foundmin) {
+				return;
+			}
+			if (foundmax) {
+				if (LESSCOST(Max, Min)) {
+					ASSIGNCOST(Max, Min);
+				}
+			} else {
+				foundmax = 1;
+				ASSIGNCOST(Max, Min);
+			}
+		}
+		break;
+		default:
+			assert(0);
+		}
+	}
+	allpairs[i ][ j].sibFlag = foundmax;
+	ASSIGNCOST(allpairs[i ][ j].sibling, Max);
+}
+
+static void
+findAllNexts()
+{
+	int i,j;
+	int last;
+
+	for (i = 1; i < max_nonterminal; i++) {
+		last = 0;
+		for (j = 1; j < max_nonterminal; j++) {
+			if (allpairs[i ][j].rule) {
+				allpairs[i ][ last].nextchain = j;
+				last = j;
+			}
+		}
+	}
+	/*
+	for (i = 1; i < max_nonterminal; i++) {
+		last = 0;
+		for (j = 1; j < max_nonterminal; j++) {
+			if (allpairs[i ][j].sibFlag) {
+				allpairs[i ][ last].nextsibling = j;
+				last = j;
+			}
+		}
+	}
+	*/
+}
+
+static Relation *
+newAllPairs()
+{
+	int i;
+	Relation *rv;
+
+	rv = (Relation*) zalloc(max_nonterminal * sizeof(Relation));
+	for (i = 0; i < max_nonterminal; i++) {
+		rv[i] = (Relation) zalloc(max_nonterminal * sizeof(struct relation));
+	}
+	return rv;
+}
+
+void
+findAllPairs()
+{
+	List pl;
+	int changes;
+	int j;
+
+	allpairs = newAllPairs();
+	for (pl = chainrules; pl; pl = pl->next) {
+		Rule p = (Rule) pl->x;
+		NonTerminalNum rhs = p->pat->children[0]->num;
+		NonTerminalNum lhs = p->lhs->num;
+		Relation r = &allpairs[lhs ][ rhs];
+
+		if (LESSCOST(p->delta, r->chain)) {
+			ASSIGNCOST(r->chain, p->delta);
+			r->rule = p;
+		}
+	}
+	for (j = 1; j < max_nonterminal; j++) {
+		Relation r = &allpairs[j ][ j];
+		ZEROCOST(r->chain);
+		r->rule = &stub_rule;
+	}
+	changes = 1;
+	while (changes) {
+		changes = 0;
+		for (pl = chainrules; pl; pl = pl->next) {
+			Rule p = (Rule) pl->x;
+			NonTerminalNum rhs = p->pat->children[0]->num;
+			NonTerminalNum lhs = p->lhs->num;
+			int i;
+
+			for (i = 1; i < max_nonterminal; i++) {
+				Relation r = &allpairs[rhs ][ i];
+				Relation s = &allpairs[lhs ][ i];
+				DeltaCost dc;
+				if (!r->rule) {
+					continue;
+				}
+				ASSIGNCOST(dc, p->delta);
+				ADDCOST(dc, r->chain);
+				if (!s->rule || LESSCOST(dc, s->chain)) {
+					s->rule = p;
+					ASSIGNCOST(s->chain, dc);
+					changes = 1;
+				}
+			}
+		}
+	}
+	findAllNexts();
+}
+
+void
+trim(t) Item_Set t;
+{
+	int m,n;
+	static short *vec = 0;
+	int last;
+
+	assert(!t->closed);
+	debug(debugTrim, printf("Begin Trim\n"));
+	debug(debugTrim, dumpItem_Set(t));
+
+	last = 0;
+	if (!vec) {
+		vec = (short*) zalloc(max_nonterminal * sizeof(*vec));
+	}
+	for (m = 1; m < max_nonterminal; m++) {
+		if (t->virgin[m].rule) {
+			vec[last++] = m;
+		}
+	}
+	for (m = 0; m < last; m++) {
+		DeltaCost tmp;
+		int j;
+		int i;
+
+		i = vec[m];
+
+		for (j = allpairs[i ][ 0].nextchain; j; j = allpairs[i ][ j].nextchain) {
+
+			if (i == j) {
+				continue;
+			}
+			if (!t->virgin[j].rule) {
+				continue;
+			}
+			ASSIGNCOST(tmp, t->virgin[j].delta);
+			ADDCOST(tmp, allpairs[i ][ j].chain);
+			if (!LESSCOST(t->virgin[i].delta, tmp)) {
+				t->virgin[i].rule = 0;
+				ZEROCOST(t->virgin[i].delta);
+				debug(debugTrim, printf("Trimmed Chain (%d,%d)\n", i,j));
+				goto outer;
+			}
+			
+		}
+		if (!trimflag) {
+			continue;
+		}
+		for (n = 0; n < last; n++) {
+			j = vec[n];
+			if (i == j) {
+				continue;
+			}
+
+			if (!t->virgin[j].rule) {
+				continue;
+			}
+
+			if (!allpairs[i][j].sibComputed) {
+				siblings(i,j);
+			}
+			if (!allpairs[i][j].sibFlag) {
+				continue;
+			}
+			ASSIGNCOST(tmp, t->virgin[j].delta);
+			ADDCOST(tmp, allpairs[i ][ j].sibling);
+			if (!LESSCOST(t->virgin[i].delta, tmp)) {
+				t->virgin[i].rule = 0;
+				ZEROCOST(t->virgin[i].delta);
+				goto outer;
+			}
+		}
+
+		outer: ;
+	}
+
+	debug(debugTrim, dumpItem_Set(t));
+	debug(debugTrim, printf("End Trim\n"));
+}
+
+void
+dumpRelation(r) Relation r;
+{
+	printf("{ %d %ld %d %ld }", r->rule->erulenum, (long) r->chain, r->sibFlag, (long) r->sibling);
+}
+
+void
+dumpAllPairs()
+{
+	int i,j;
+
+	printf("Dumping AllPairs\n");
+	for (i = 1; i < max_nonterminal; i++) {
+		for (j = 1; j < max_nonterminal; j++) {
+			dumpRelation(&allpairs[i ][j]);
+		}
+		printf("\n");
+	}
+}
diff --git a/llvm/utils/Burg/zalloc.c b/llvm/utils/Burg/zalloc.c
new file mode 100644
index 00000000000..9128e4280f2
--- /dev/null
+++ b/llvm/utils/Burg/zalloc.c
@@ -0,0 +1,35 @@
+char rcsid_zalloc[] = "$Id$";
+
+#include <stdio.h>
+#include <string.h>
+#include "b.h"
+
+extern void exit ARGS((int));
+extern void free ARGS((void *));
+extern void *malloc ARGS((unsigned));
+
+int
+fatal(const char *name, int line)
+{
+	fprintf(stderr, "assertion failed: file %s, line %d\n", name, line);
+	exit(1);
+	return 0;
+}
+
+void *
+zalloc(size) unsigned int size;
+{
+	void *t = (void *) malloc(size);
+	if (!t) {
+		fprintf(stderr, "Malloc failed---PROGRAM ABORTED\n");
+		exit(1);
+	}
+	memset(t, 0, size);
+	return t;
+}
+
+void
+zfree(p) void *p;
+{
+	free(p);
+}