Move support/tools/* back into utils
llvm-svn: 8875
diff --git a/llvm/utils/Burg/COPYRIGHT b/llvm/utils/Burg/COPYRIGHT
new file mode 100644
index 0000000..1de0aad
--- /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 0000000..226210d
--- /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 0000000..0f7c13f
--- /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 0000000..3211f32
--- /dev/null
+++ b/llvm/utils/Burg/Doc/doc.dvi
Binary files differ
diff --git a/llvm/utils/Burg/Doc/doc.log b/llvm/utils/Burg/Doc/doc.log
new file mode 100644
index 0000000..a224a4e
--- /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 0000000..3dc67be
--- /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 0000000..804f003
--- /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 0000000..5797161
--- /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 0000000..bc26405
--- /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 0000000..164325d
--- /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 0000000..defe948
--- /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 0000000..173bbfd
--- /dev/null
+++ b/llvm/utils/Burg/burg.shar.gz
Binary files differ
diff --git a/llvm/utils/Burg/burs.c b/llvm/utils/Burg/burs.c
new file mode 100644
index 0000000..b4f8b83
--- /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 0000000..70e1626
--- /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 0000000..d796549
--- /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 0000000..36b373d
--- /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 0000000..1c7b2fe
--- /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 0000000..9d2f9f4
--- /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 0000000..4a9f4a3
--- /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 0000000..85eb8a7
--- /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 0000000..d3eefa2
--- /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 0000000..dbfdbf4
--- /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 0000000..588b485
--- /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 0000000..71fd7d4
--- /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 0000000..a6df9e3
--- /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 0000000..472aca5
--- /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 0000000..1ce006d
--- /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 0000000..76e5ea9
--- /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 0000000..ee5c89e
--- /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 0000000..e1f7283
--- /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 0000000..9b69c30
--- /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 0000000..3ecab2f
--- /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 0000000..1de74f9
--- /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 0000000..05ee2d0
--- /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 0000000..9128e42
--- /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);
+}