\batchmode
\documentstyle[html,11pt,tgrind,vi]{mitthesis}
\makeatletter
%



\let\underscore=\_
\catcode`_=13
\def_{\underscore\penalty75\relax}
%

%

%


%
\widowpenalty=10000 %
\clubpenalty=10000 %


%

%



\newenvironment {snippet}{\begin{center}\begin{small}\begin{singlespace}\begin{minipage}[t]{5.5in}\rule{5.5in}{1pt}\vspace{\baselineskip}}{\rule{5.5in}{1pt}\end{minipage}\end{singlespace}\end{small}\end{center}\vspace{-11pt}}

\newcommand {\supc}[1]{$^{\rm #1}$}

\def\cpp/{C\verb|++|}

\def\etc/{\sl [....] \par}

\newcommand {\qed}{\rule{7pt}{7pt}}

\newcommand {\tab}{\hspace*{0.5in}}

\makeatother
\newenvironment{tex2htmlwrap}{}{}
\newwrite\lthtmlwrite
\def\lthtmltypeout#1{{\let\protect\string\immediate\write\lthtmlwrite{#1}}}%
\newbox\sizebox
\begin{document}
\pagestyle{empty}
{\newpage
\clearpage
\samepage \begin{singlespace}\begin{latexonly}

\vspace*{\baselineskip}
This research and the Reinventing Computing group at the MIT
Artificial Intelligence Laboratory are supported in part by the
Advanced Research Projects Agency of the Department of Defense, under
Rome Labs contract number F30602-94-C-0252.

\vspace*{\baselineskip}
The bulk of this thesis has been inspired by numerous technical notes
of the Transit project, the predecessor to the Reinventing Computing
group.  I especially wish to acknowledge the influence of discussions
with Andr\'e DeHon.  I'd like to thank my thesis advisor Thomas F.\
Knight, Jr., for his faith in giving me free rein on my thesis work.
Without the research assistantship funding, paying tuition for a fifth
year for my master of engineering degree would have been very painful.
I would also like to thank Ian Eslick and Jeremy Brown, other graduate
students in the Reinventing Computing group, for their comments,
feedback, and moral support.

\vspace*{\baselineskip}
Over the last five years, making time to go on community service
projects with Alpha Phi Omega, be it painting at a homeless shelter or
wielding power tools of destruction at a Boy Scout camp, contributed
greatly to the retention of my sanity.  It is healthy to be reminded
that there are more important things out there in the real world than
passing classes or finishing thesis.

\vspace*{\baselineskip}
The hundreds of hours sitting at my keyboard during the last several
terms passed less painfully thanks to the music of the Chorallaries
and Logarhythms (MIT a capella singing groups), whose albums took up
semi-permanent residence in the CD-ROM drive on my workstation.  Also,
while it's not clear that this particular acknowledgement is in the
form of a thank you, I should acknowledge the quality soft drink
products of the Coca-Cola company, many scores of liters of which I
consumed in front of said keyboard.

\vspace*{\baselineskip}
Last but not least, I would like to thank my parents, who came to a
foreign country to give better opportunities to my sister and me; and
my friends, who tolerably tolerated my complaints this past year about
the job search process and thesis --- Kate and Barbara especially come
to mind.

\vfill
\hrule
\vspace*{\baselineskip}
\noindent Comments, corrections, and feedback are welcome via e-mail to
{\tt pshuang@MIT.EDU}.
\vspace*{\baselineskip}

\end{latexonly}
\end{singlespace}
}

\stepcounter{chapter}
\stepcounter{section}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$^{\rm ST}$}\lthtmltypeout{latex2htmlSize :tex2htmlwrapinline2066: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\stepcounter{section}
{\newpage
\clearpage
\samepage \begin{figure}\begin{center}

\setlength{\unitlength}{0.0125in}%
\begin{picture}(480,480)(20,350)
\thicklines
\put(360,760){\oval(80,40)}
\put(160,700){\oval(80,40)}
\put(160,480){\oval(80,40)}
\put(360,480){\oval(80,40)}
\put(360,540){\oval(80,40)}
\put(360,420){\oval(80,40)}
\put(360,640){\oval(80,40)}
\put(460,480){\oval(80,40)}
\put(460,700){\oval(80,40)}
\put(360,700){\oval(80,40)}
\put(100,700){\vector( 1, 0){ 20}}
\put(200,700){\vector( 1, 0){ 20}}
\put(300,700){\vector( 1, 0){ 20}}
\put(400,700){\vector( 1, 0){ 20}}
\put(360,740){\vector( 0,-1){ 20}}
\put(360,680){\vector( 0,-1){ 20}}
\put(100,480){\vector( 1, 0){ 20}}
\put(200,480){\vector( 1, 0){ 20}}
\put(300,480){\vector( 1, 0){ 20}}
\put(400,480){\vector( 1, 0){ 20}}
\put(360,520){\vector( 0,-1){ 20}}
\put(360,460){\vector( 0,-1){ 20}}
\put(460,460){\line( 0,-1){ 80}}
\put(460,380){\line(-1, 0){200}}
\put(260,380){\vector( 0, 1){ 80}}
\put(460,720){\line( 0, 1){ 80}}
\put(460,800){\line(-1, 0){400}}
\put( 60,800){\vector( 0,-1){ 80}}
\put(220,680){\framebox(80,40){}}
\put( 20,460){\framebox(80,40){}}
\put( 20,680){\framebox(80,40){}}
\put( 20,350){\line( 1, 0){480}}
\put( 20,590){\line( 1, 0){480}}
\put( 20,830){\line( 1, 0){480}}
\put(320,680){\framebox(80,40){}}
\put(320,460){\framebox(80,40){}}
\put(220,460){\framebox(80,40){}}
\put(260,460){\makebox(0.4444,0.6667){\tenrm .}}
\put( 80,385){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\svtnrm FEEDBACK MODEL}}}
\put( 80,405){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\svtnrm SMART COMPILER}}}
\put( 80,780){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\svtnrm TRADITIONAL MODEL}}}
\put(330,765){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\tenrm Programmer}}}
\put(325,752){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\tenrm selected input}}}
\put(235,692){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm compiler}}}
\put(230,705){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm Optimizing}}}
\put(340,645){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm Program}}}
\put(345,632){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm output}}}
\put( 25,700){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm Programmer}}}
\put( 25,480){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm Programmer}}}
\put(125,480){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm Source code}}}
\put(125,700){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm Source code}}}
\put(235,472){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm compiler}}}
\put(240,485){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm Smart}}}
\put(330,532){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm to program}}}
\put(330,545){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm User input}}}
\put(335,705){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm Program}}}
\put(330,692){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm executable}}}
\put(335,485){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm Program}}}
\put(330,472){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm executable}}}
\put(335,425){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm Program}}}
\put(340,412){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm output}}}
\put(435,485){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm Profiling}}}
\put(445,472){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm data}}}
\put(435,705){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm Profiling}}}
\put(445,692){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm data}}}
\end{picture}
%

\end{center}

\label{figure:feedback}
\end{figure}
}

\stepcounter{chapter}
\stepcounter{section}
{\newpage
\clearpage
\samepage \begin{singlespace}\fbox{\parbox{4.5in}{
\vspace{5pt}
\tab {\it quasistatic-variable-declaration}: \\ 
\tab \tab {\tt qvar} {\it identifier}

\tab {\it qif-statement}: \\ 
\tab \tab {\tt qif (} {\it quasistatic-variable} {\tt )} {\it statement} \\ 
\tab \tab {\it qif-statement}\/ {\tt qelse} {\it qif-statement} \\ 
\tab \tab {\it qif-statement}\/ {\tt qelse} {\it statement}
\vspace{5pt}
}}
\end{singlespace}
}

{\newpage
\clearpage
\samepage \begin{figure}\begin{center}\begin{small}\begin{singlespace}\begin{minipage}[t]{5.5in}\rule{5.5in}{1pt}\vspace{\baselineskip}\begin{verbatim}qif(SPECIAL_SORT_INPUT) {
  FOOBARsort(array,N,....,compare_elements);
}
qelse {
  quicksort(array,N,....,compare_elements);
}
\end{verbatim}
\rule{5.5in}{1pt}\end{minipage}\end{singlespace}\end{small}\end{center}\vspace{-11pt}


\label{figure:qif-sorting}
\end{figure}
}

{\newpage
\clearpage
\samepage \begin{figure}\begin{center}\begin{small}\begin{singlespace}\begin{minipage}[t]{5.5in}\rule{5.5in}{1pt}\vspace{\baselineskip}\begin{verbatim}qif(FULL_HW_ASSIST) {
  communicate_display_list(....);
  /* Pass the display list to the accelerator and tell it to do all
     the rendering. */
}
qelse qif(PARTIAL_HW_ASSIST) {
  process_display_list(....);
  /* Iterate over the display list, decompose each graphics object
     into simpler commands, perform z-order clipping, and then hand the
     commands to the accelerator. */
}
qelse {
  render_display_list(....);
  copy_to_screen(....);
  /* Render the display list into a bitmap, and then send the result
     to the dumb graphics device. */
}
\end{verbatim}
\rule{5.5in}{1pt}\end{minipage}\end{singlespace}\end{small}\end{center}\vspace{-11pt}


\label{figure:qif-hw-assist}
\end{figure}
}

\stepcounter{section}
{\newpage
\clearpage
\samepage \begin{singlespace}\fbox{\parbox{4.5in}{
\vspace{5pt}
\tab {\it qint-parameter-definition}: \\ 
\tab \tab {\tt qint [} {\it qint-range-list} {\tt ]} {\it identifier}

\tab {\it qint-range-list}: \\ 
\tab \tab {\it qint-range-specifier} \\ 
\tab \tab {\it qint-range-list} {\tt ,} {\it qint-range-specifier}

\tab {\it qint-range-specifier}: \\ 
\tab \tab {\it integer-constant} \\ 
\tab \tab {\it integer-constant} {\tt :} {\it integer-constant}

\tab {\it qinfluence-statement}: \\ 
\tab \tab {\tt qinfluence (} {\it qint-parameter} {\tt )} {\it statement}
\vspace{5pt}
}}
\end{singlespace}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{${\tt BLOCK_SIZE}=1024$}\lthtmltypeout{latex2htmlSize :tex2htmlwrapinline2122: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{${\tt
BLOCK_SIZE}=4096$}\lthtmltypeout{latex2htmlSize :tex2htmlwrapinline2124: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{${\tt BLOCK_SIZE}=2048$}\lthtmltypeout{latex2htmlSize :tex2htmlwrapinline2126: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{figure}\begin{center}\begin{small}\begin{singlespace}\begin{minipage}[t]{5.5in}\rule{5.5in}{1pt}\vspace{\baselineskip}\begin{verbatim}qint[1024,2048,4096] BLOCK_SIZE;
\end{verbatim}
\etc/
\begin{verbatim}BlockedMultiply(MatrixA, MatrixB, ResultMatrix, BLOCK_SIZE);
\end{verbatim}
\rule{5.5in}{1pt}\end{minipage}\end{singlespace}\end{small}\end{center}\vspace{-11pt}


\label{figure:qint-matrix-multiply1}
\end{figure}
}

{\newpage
\clearpage
\samepage \begin{figure}\begin{center}\begin{small}\begin{singlespace}\begin{minipage}[t]{5.5in}\rule{5.5in}{1pt}\vspace{\baselineskip}\begin{verbatim}qint[10:12] BLOCK_SIZE_SHIFT;
#define BLOCK_SIZE (1<<BLOCK_SIZE_SHIFT)
\end{verbatim}
\etc/
\begin{verbatim}BlockedMultiply(MatrixA, MatrixB, ResultMatrix, BLOCK_SIZE);
\end{verbatim}
\rule{5.5in}{1pt}\end{minipage}\end{singlespace}\end{small}\end{center}\vspace{-11pt}


\label{figure:qint-matrix-multiply2}
\end{figure}
}

{\newpage
\clearpage
\samepage \begin{figure}\begin{center}\begin{small}\begin{singlespace}\begin{minipage}[t]{5.5in}\rule{5.5in}{1pt}\vspace{\baselineskip}\begin{verbatim}{
  qint[1024,4096,16384,65536] USE_REMOTE_COMPUTATION_SERVER_LIMIT;
  qint[1:8] REMOTE_PIECES;
  qint[16,64,256] LOCAL_BLOCK_SIZE;

  if (size_of_data < USE_REMOTE_COMPUTATION_SERVER_LIMIT)
    /* Partition data into LOCAL_BLOCK_SIZE-sized blocks
       and process locally */
  else
    /* Partition data into REMOTE_PIECES number of pieces and
       send each piece to a remote computation servers for processing */
}
\end{verbatim}
\rule{5.5in}{1pt}\end{minipage}\end{singlespace}\end{small}\end{center}\vspace{-11pt}


\label{figure:qint-client-server1}
\end{figure}
}

{\newpage
\clearpage
\samepage \begin{figure}\begin{center}\begin{small}\begin{singlespace}\begin{minipage}[t]{5.5in}\rule{5.5in}{1pt}\vspace{\baselineskip}\begin{verbatim}{
  qint[1024,4096,16384] USE_REMOTE_COMPUTATION_SERVER_LIMIT;
  qint[1:8] REMOTE_PIECES;
  qint[16,64,256] LOCAL_BLOCK_SIZE;

  if (size_of_data < USE_REMOTE_COMPUTATION_SERVER_LIMIT);
    qinfluence(LOCAL_BLOCK_SIZE) {
      /* Partition data into LOCAL_BLOCK_SIZE-sized blocks
         and process locally */
    }
  else
    qinfluence(REMOTE_PIECES) {
      /* Partition data into REMOTE_PIECES number of pieces and
         ship to a remote computation server to processing */
    }
}
\end{verbatim}
\rule{5.5in}{1pt}\end{minipage}\end{singlespace}\end{small}\end{center}\vspace{-11pt}


\label{figure:qint-client-server2}
\end{figure}
}

\stepcounter{section}
\stepcounter{paragraph}
\stepcounter{paragraph}
\stepcounter{paragraph}
\stepcounter{chapter}
{\newpage
\clearpage
\samepage \begin{figure}\begin{center}

\setlength{\unitlength}{0.0125in}%
\begin{picture}(340,420)(20,400)
\thicklines
\put(100,780){\oval(80,40)}
\put(200,700){\oval(80,40)}
\put(200,580){\oval(80,40)}
\put(300,440){\oval(80,40)}
\put(100,640){\oval(80,40)}
\put( 40,480){\framebox(220,260){}}
\put(100,760){\vector( 0,-1){ 40}}
\put(140,700){\vector( 1, 0){ 20}}
\put(200,680){\vector( 0,-1){ 20}}
\put(100,620){\vector( 0,-1){ 20}}
\put(140,580){\vector( 1, 0){ 20}}
\put(200,560){\vector( 0,-1){ 20}}
\put(200,500){\vector( 0,-1){ 40}}
\put(240,440){\vector( 1, 0){ 20}}
\put(300,460){\line( 0, 1){180}}
\put(300,640){\vector(-1, 0){ 60}}
\put( 60,680){\framebox(80,40){}}
\put( 60,560){\framebox(80,40){}}
\put(160,500){\framebox(80,40){}}
\put(160,620){\framebox(80,40){}}
\put(160,420){\framebox(80,40){}}
\put( 20,400){\framebox(340,420){}}
\put(160,640){\vector(-1, 0){ 20}}
\put(100,660){\line( 0, 1){ 10}}
\put(100,670){\line( 1, 0){ 80}}
\put(180,670){\vector( 0,-1){ 10}}
\put( 70,785){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm Annotated}}}
\put( 75,772){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm C source}}}
\put( 75,692){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm front end}}}
\put( 65,705){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\tenrm Modified SUIF}}}
\put( 75,645){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm Modified}}}
\put( 75,630){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm SUIF file}}}
\put( 75,585){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm SUIF s2c}}}
\put( 75,570){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm back-end}}}
\put(165,512){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\tenrm \& profiling lib.}}}
\put(165,525){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\tenrm GCC compiler}}}
\put(170,645){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm New SUIF}}}
\put(180,632){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm passes}}}
\put(175,700){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm SUIF file}}}
\put(165,445){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\elvrm Instrumented}}}
\put(170,432){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm executable}}}
\put(275,445){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm Profiling}}}
\put(285,432){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm data}}}
\put(160,765){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\svtnrm IMPLEMENTATION}}}
\put(160,785){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\svtnrm CLEVER COMPILER}}}
\put(170,585){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\tenrm Standard C}}}
\put(170,572){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\tenrm source code}}}
\end{picture}
%

\end{center}

\label{figure:system}
\end{figure}
}

\stepcounter{section}
{\newpage
\clearpage
\samepage \begin{table}\begin{center}
\begin{tabular}{|r||c|c|c|c|c|}
\hline
Compiler & Source code & Wide Use & Competitive & Cross-platform & Easy mod. \\ 
\hline
\hline
{\tt lcc} & Yes   & No    & $^{\rm (A)}$
    & Yes           & Yes \\ 
\hline
{\tt gcc} & Yes   & Yes   & Yes           & Yes           & No \\ 
\hline
SUIF      & Yes   & No    & $^{\rm (A)}$
    & $^{\rm (B)}$
    & Yes \\ 
\hline
Vendor    & No    & Yes   & Yes           & No            & No $^{\rm (C)}$
 \\ 
\hline
C-to-C    & Yes   & No    & N/A           & $^{\rm (B)}$
   & Yes \\ 
\hline
\end{tabular}
\end{center}

%




\begin{scriptsize}
\begin{singlespace}
\noindent (A) Claims are that output programs' performance are
  approximately 70--90\% that of the best available compilers. \\ 
\noindent (B) SUIF only has a back-end code generator for MIPS;
  however, it and C-to-C qualify as cross-platform since they can
  be used as source-to-source compilers. \\ 
\noindent (C) Some vendor compilers may actually be easy to modify;
  my {\em speculation} is that most of them, for performance sake, are
  not architected to be easily modifiable (e.g., separate passes).
\end{singlespace}
\end{scriptsize}

\label{table:compilers}
\end{table}
}

\stepcounter{section}
{\newpage
\clearpage
\samepage \begin{figure}\begin{center}\begin{small}\begin{singlespace}\begin{minipage}[t]{5.5in}\rule{5.5in}{1pt}\vspace{\baselineskip}\begin{verbatim}qint[10,20,30] EXIT_CODE_BASE;

void foo(void) {
  qinfluence(EXIT_CODE_BASE) {
    qif(FIRST_ALTERNATIVE)
      { exit(1 + EXIT_CODE_BASE); }
    qelse qif(SECOND_ALTERNATIVE)
      { exit(2 + EXIT_CODE_BASE); }
    qelse
      { exit(3 + EXIT_CODE_BASE); }
  }
}
\end{verbatim}
{\rule{5.5in}{1pt}\end{minipage}\end{singlespace}\end{small}\end{center}\vspace{-11pt}}

\label{figure:snoot-example}
\end{figure}
}

{\newpage
\clearpage
\samepage \begin{figure}\begin{center}\begin{small}\begin{singlespace}\begin{minipage}[t]{5.5in}\rule{5.5in}{1pt}\vspace{\baselineskip}\etc/
\begin{scriptsize}

\begin{verbatim}extern const int EXIT_CODE_BASE /* ["QINT PARAMETER"] */;
extern void foo(void);
extern const int FIRST_ALTERNATIVE /* ["QIF VARIABLE"] */;
extern int exit();
extern const int SECOND_ALTERNATIVE /* ["QIF VARIABLE"] */;

const int EXIT_CODE_BASE;

extern void foo(void)
  {
    {
      const int QINFLUENCE_BLOCK_HOLDER;

      if /* ["QIF STATEMENT"] */ (FIRST_ALTERNATIVE != 0)
        {
          exit(1 + EXIT_CODE_BASE);
        }
      else
        {
          if /* ["QIF STATEMENT"] */ (SECOND_ALTERNATIVE != 0)
            {
              exit(2 + EXIT_CODE_BASE);
            }
          else
            {
              exit(3 + EXIT_CODE_BASE);
            }
        }
    } /* ["QINFLUENCE STATEMENT"] */
    return;
  }
\end{verbatim}
\end{scriptsize}
{\rule{5.5in}{1pt}\end{minipage}\end{singlespace}\end{small}\end{center}\vspace{-11pt}}

\label{figure:snoot-s2c}
\end{figure}
}

\stepcounter{section}
{\newpage
\clearpage
\samepage \begin{figure}\begin{center}\begin{small}\begin{singlespace}\begin{minipage}[t]{5.5in}\rule{5.5in}{1pt}\vspace{\baselineskip}\begin{verbatim}int foo(void)
{
  int bar = 0;
  qif(ALTERNATIVE_1)
    { bar = 1; }
  qelse qif(ALTERNATIVE_2)
    { bar = 2; }

  qif(ALTERNATIVE_1)
    { bar += foo(); }
  qelse
    { bar -= foo(); }

  return bar;
}

void partition_work(int);
void dispatch_work_to_new_thread(void);

qint[1024,4096,16384] BLOCK_SIZE;
qint[1:8] THREADS;

void process(void)
{
  qinfluence(BLOCK_SIZE)
    {
      partition_work(BLOCK_SIZE);
      qinfluence(THREADS)
        {
          int index;
          for (index=0; index<THREADS; index++)
            create_new_thread();
          wait_for_threads_finish();
        }
    }
}
\end{verbatim}
{\rule{5.5in}{1pt}\end{minipage}\end{singlespace}\end{small}\end{center}\vspace{-11pt}}

\label{figure:sets-source}
\end{figure}
}

{\newpage
\clearpage
\samepage \begin{figure}\begin{center}\begin{small}\begin{singlespace}\begin{minipage}[t]{5.5in}\rule{5.5in}{1pt}\vspace{\baselineskip}\etc/
\begin{verbatim}    Global symbol table: `globals'
\end{verbatim}
\etc/
\begin{verbatim}      Annotations:
        ["QINFLUENCE SET": 0 "BLOCK_SIZE"]
        ["QINFLUENCE SET": 1 "THREADS" "BLOCK_SIZE"]
        ["QIF SET": 2 "ALTERNATIVE_1" "... FINAL QELSE"]
        ["QIF SET": 3 "ALTERNATIVE_2" "ALTERNATIVE_1" "... NO FINAL QELSE"]
\end{verbatim}
\etc/
\vspace{7pt}
\rule{5.5in}{1pt}\end{minipage}\end{singlespace}\end{small}\end{center}\vspace{-11pt}


\label{figure:sets-annotations}
\end{figure}
}

{\newpage
\clearpage
\samepage \begin{figure}\begin{center}\begin{small}\begin{singlespace}\begin{minipage}[t]{5.5in}\rule{5.5in}{1pt}\vspace{\baselineskip}\begin{verbatim}qint[1:8] QUX;

void A(void)
{
  qif(FOO)
    { B(); }
  qelse qif(BAR)
    { C(); }
}

void B(void)
{
  qinfluence(QUX)
    { /* .... */ }
}
\end{verbatim}
\rule{5.5in}{1pt}\end{minipage}\end{singlespace}\end{small}\end{center}\vspace{-11pt}


\label{figure:dynamic-nesting}
\end{figure}
}

\stepcounter{section}
{\newpage
\clearpage
\samepage \begin{singlespace}The `ideal system of the future' will keep profiles associated with
source programs, using the frequency counts in virtually all phases of
a program's life.  \ldots[I]f it is to be a frequently used program
the high counts in its profile often suggest basic improvements which
can be made.  An optimizing compiler can also make very effective use
of the profile, since it often suffices to do time-consuming
optimization on only one-tenth or one-twentieth of a program. \par
\end{singlespace}
}

{\newpage
\clearpage
\samepage \begin{table}% latex2html id marker 969
\begin{center}
\begin{tabular}{||r||r|r||c||}
\hline
{\small Profiling type} &
{\small User time (sec.)} &
{\small System time (sec.)} &
{\small Added overhead (\%)} \\ 
\hline
\hline
{\bf DECstation/Ultrix} $^{\rm (A)}$
 & 74.1 & 0.8 & {\bf 0.0\%} \\ 
%


\hline
prof ({\tt gcc -p}) & 83.1 & 0.7 & 11.9\% \\ 
%


\hline
pixie & 197.7 & 1.5 & 165.0\% \\ 
%









\hline
\hline
{\bf Pentium/Linux} $^{\rm (B)}$
 & 19.9 & 0.3 & {\bf 0.0\%} \\ 
%


\hline
gprof ({\tt gcc -pg}) & 22.6 & 0.3 & 13.3\% \\ 
%


\hline
\hline
{\bf SPARC/SunOS} $^{\rm (C)}$
 & 21.2 & 0.3 & {\bf 0.0\%} \\ 
%


\hline
prof ({\tt gcc -p}) & 22.2 & 0.2 & 4.2\% \\ 
%


\hline
gprof ({\tt gcc -pg}) & 23.7 & 0.3 & 11.6\% \\ 
%


\hline
\end{tabular}
\end{center}

\begin{scriptsize}
\begin{singlespace}
\noindent (A) DECstation 5000/25: MIPS 25Mhz R3000 with 24MB
  memory running Ultrix 4.3; GNU {\tt gcc} compiler version 2.5.90.
  Running in multi-user mode, but with only one user.  On this
  platform, {\tt gprof} profiling was not available since the vendor
  supports {\tt pixie}, which provides a superset of the functionality
  of {\tt gprof}. \\ 
\noindent (B) Dell XPS P90: see \pageref{chapter:examples} for system
  configuration.  On this platform, requesting {\tt prof} profiling
  ended up performing {\tt gprof} profiling; hence numbers are only
  reported for the latter style.  {\tt pixie} profiling was not
  available. \\ 
\noindent (C) Sun SPARCstation 20: TIS390Z50 CPU with 64MB memory
  running SunOS 4.1.3; GNU {\tt gcc} compiler version 2.5.7.  Running
  in multi-user mode, but with only one user.  {\tt pixie} profiling
  was not available.
\end{singlespace}
\end{scriptsize}


\label{table:profiling-overhead}
\end{table}
}

{\newpage
\clearpage
\samepage \begin{singlespace}\ldots{}a TICK register has been added, which is incremented once per
machine cycle.  This register can be read by a user's application to
make simple and accurate measurements of program performance.''
\end{singlespace}
}

{\newpage
\clearpage
\samepage \begin{table}% latex2html id marker 1062
\begin{center}
\begin{tabular}{|c|r|}
\hline
Description & Cycles \\ 
\hline
\hline
1 call to trivial function			& 55 \\ 
\hline
1 ``call'' to {\tt inline}'ed function		& 0 \\ 
\hline
\hline
1,000 calls to trivial function			& 13,000 \\ 
\hline
1,000 ``calls'' to {\tt inline}'ed function	& 0 \\ 
\hline
\hline
Start, stop, and update stopwatch counter	& 57 \\ 
\hline
\end{tabular}
\end{center}

\begin{scriptsize}
\begin{singlespace}
Results have been normalized to take into account that attempting to
profile a null code sequence resulted in a count of 13 cycles, due to
the exact placement of the actual {\tt RDTSC} instruction in the
profiling prologue and epilogue.
\end{singlespace}
\end{scriptsize}

\label{table:test-rdtsc}
\end{table}
}

{\newpage
\clearpage
\samepage \begin{singlespace}\fbox{\parbox{2.5in}{
\tab {\tt return} {\it expression} {\tt ;}
}}
\end{singlespace}
}

{\newpage
\clearpage
\samepage \begin{singlespace}\fbox{\parbox{2.5in}{
\tab {\tt suif_tmp0 =} {\it expression} {\tt ; \\ 
\tab qp_stop(} {\it UID} {\tt ); \\ 
\tab return suif_tmp0};
}}
\vspace{\baselineskip}
\end{singlespace}
}

{\newpage
\clearpage
\samepage \begin{figure}\begin{center}\begin{small}\begin{singlespace}\begin{minipage}[t]{5.5in}\rule{5.5in}{1pt}\vspace{\baselineskip}\begin{verbatim}#include <stdio.h>
#include <stdlib.h>
#include "qprofiling.h"

qint[1:32000] WAIT_LENGTH;

int main(int argc, char *argv[]) {
  printf("Hello, ");
  qinfluence(WAIT_LENGTH) {
    qif(DO_WAIT) {
      sleep(WAIT_LENGTH);
      printf(", world. (Yawn.)\n");
      return WAIT_LENGTH;
    }
    qelse qif(DONT_WAIT) {
      printf("world.\n");
    }
  }
  qif(DO_WAIT) {
    printf("Did you think I fell asleep?\n");
  }
  qelse qif(DONT_WAIT) {
    printf("See, I'm wide awake!\n");
  }
}
\end{verbatim}
{\rule{5.5in}{1pt}\end{minipage}\end{singlespace}\end{small}\end{center}\vspace{-11pt}}

\label{figure:hello-c}
\end{figure}
}

{\newpage
\clearpage
\samepage \begin{figure}\begin{center}\begin{small}\begin{singlespace}\begin{minipage}[t]{5.5in}\rule{5.5in}{1pt}\vspace{\baselineskip}\begin{scriptsize}

\etc/
\vspace{-\baselineskip}
\begin{verbatim}const int WAIT_LENGTH = 1;
const int DO_WAIT;
const int DONT_WAIT = 1;
\end{verbatim}
\vspace{-\baselineskip}
\etc/
\vspace{-\baselineskip}
\begin{verbatim}extern int main(int argc, char **argv)
  {
    int suif_tmp0;
    int suif_tmp1;

    qp_initialize("hello.prf", 2, 0);
    printf("Hello, ");
      {
        const int QINFLUENCE_BLOCK_HOLDER;
        qp_start(0, 0);
        if (DO_WAIT != 0)
          {
            qp_start(1, 0);
            sleep(WAIT_LENGTH);
            printf(", world. (Yawn.)\n");
            suif_tmp0 = WAIT_LENGTH;
            qp_stop(0, 0);
            qp_stop(1, 0);
            qp_dump(0);
            return suif_tmp0;
            qp_stop(1, 0);
          }
        else
          {
            if (DONT_WAIT != 0)
              {
                qp_start(1, 0);
                printf("world.\n");
                qp_stop(1, 0);
              }
          }
        qp_stop(0, 0);
      }
    if (DO_WAIT != 0)
      {
        qp_start(1, 0);
        printf("Did you think I fell asleep?\n");
        qp_stop(1, 0);
      }
    else
      {
        if (DONT_WAIT != 0)
          {
            qp_start(1, 0);
            printf("See, I'm wide awake!\n");
            qp_stop(1, 0);
          }
      }
    suif_tmp1 = 0;
    qp_dump(0);
    return suif_tmp1;
    qp_dump(0);
  }
\end{verbatim}
\vspace{-\baselineskip}
\end{scriptsize}
{\rule{5.5in}{1pt}\end{minipage}\end{singlespace}\end{small}\end{center}\vspace{-11pt}}

\label{figure:hello-prf-s2c}
\end{figure}
}

\stepcounter{section}
\stepcounter{paragraph}
\stepcounter{paragraph}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$t(a,b,c)$}\lthtmltypeout{latex2htmlSize :tex2htmlwrapinline2168: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$t(a,b,c)=f(a,b)+g(c)$}\lthtmltypeout{latex2htmlSize :tex2htmlwrapinline2180: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$f(a,b)$}\lthtmltypeout{latex2htmlSize :tex2htmlwrapinline2182: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$g(c)$}\lthtmltypeout{latex2htmlSize :tex2htmlwrapinline2184: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$t(a1,b1,c1) < t(a1,b1,c2) < t(a1,b1,c3)$}\lthtmltypeout{latex2htmlSize :tex2htmlwrapinline2186: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$t(a1,b1,c1) < t(a1,b1,c3)$}\lthtmltypeout{latex2htmlSize :tex2htmlwrapinline2192: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$t(a,b,c)$}\lthtmltypeout{latex2htmlSize :tex2htmlwrapinline2194: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\stepcounter{paragraph}
\stepcounter{section}
{\newpage
\clearpage
\samepage \begin{singlespace}\begin{enumerate}
\itemsep=-3pt
\item Pore over the program and restructure it to take advantage of
  quasistatic variables and parameters and quasistatic {\tt qif-qelse}
  and {\tt qinfluence} statements.
\item Add the statement \verb+#include "qprofiling.h"+ to {\tt prog.c}
  before the use of any quasistatic constructs.
\item Invokes the {\tt make} utility on the target {\tt prog.exe},
  pointing it at an appropriate makefile which knows to run the
  following commands:
    \begin{itemize}
    \item {\tt scc -.i prog.c} (invokes the C preprocessor)
    \item {\tt snoot prog.i prog.snt}
    \item {\tt porky prog.snt prog.spd}
    \item {\tt integrate prog.spd prog.int}
    \item {\tt add_profiling prog.int prog.prf}
    \item {\tt select_alternatives prog.prf _some_tmp_file_}
    \item {\tt create_executable prog.prf}
    \end{itemize}
\item Hand off the executable {\tt prog.prf.exe} created by the {\tt
  create_executable} pass to the end-user, Ben Bitdiddle.

  [At this point, Alyssa decides to take some of her well-deserved
  vacation time and leaves for the hackers conference conveniently
  sited in Tahiti.]
\end{enumerate}
\end{singlespace}
}

\stepcounter{chapter}
\stepcounter{section}
{\newpage
\clearpage
\samepage \begin{singlespace}\begin{verbatim}2.4: Other performance characteristics: EQNTOTT dynamically allo-
cates  about  1.8 megabytes of memory in 450 calls to the library
routine malloc, when run with the int_pri_3.eqn input  file.   In
addition,  the benchmark spends nearly 95% of its time in the li-
brary routine qsort.
\end{verbatim}
\end{singlespace}
}

\stepcounter{subsection}
{\newpage
\clearpage
\samepage \begin{table}\begin{center}
\begin{tabular}{|c|c|r|r|}
\hline
Sort type  & Input is\ldots & Sort time (sec.) & Compares (millions) \\ 
\hline
\hline
Quicksort  & unsorted               & 55.73 & 115.726 \\ 
\hline
Merge sort & unsorted               & 60.04 &  93.372 \\ 
\hline
\hline
Quicksort  & already sorted         & 28.87 &  95.000 \\ 
\hline
Merge sort & already sorted         & 30.29 &  49.425 \\ 
\hline
\end{tabular}
\end{center}

\label{table:sorting-times}
\end{table}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$^2$}\lthtmltypeout{latex2htmlSize :tex2htmlwrapinline2210: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$^2$}\lthtmltypeout{latex2htmlSize :tex2htmlwrapinline2212: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\stepcounter{subsection}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\{aa==bb\}$}\lthtmltypeout{latex2htmlSize :tex2htmlwrapinline2214: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\{aa==0,~bb==2\}$}\lthtmltypeout{latex2htmlSize :tex2htmlwrapinline2216: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\{aa==2,~bb==0\}$}\lthtmltypeout{latex2htmlSize :tex2htmlwrapinline2218: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\{aa==0,~bb==2\}$}\lthtmltypeout{latex2htmlSize :tex2htmlwrapinline2220: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\{aa==2,~bb==0\}$}\lthtmltypeout{latex2htmlSize :tex2htmlwrapinline2222: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{figure}\begin{center}\begin{small}\begin{singlespace}\begin{minipage}[t]{5.5in}\rule{5.5in}{1pt}\vspace{\baselineskip}\begin{verbatim}if (aa == 2)
  aa = 0;
if (bb == 2)
  bb = 0;
if (aa != bb) {
  if (aa < bb) {
    return (-1);
  }
  else {
    return (1);
  }
\end{verbatim}
\rule{5.5in}{1pt}\end{minipage}\end{singlespace}\end{small}\end{center}\vspace{-11pt}


\label{figure:cmppt-original}
\end{figure}
}

{\newpage
\clearpage
\samepage \begin{figure}\begin{center}\begin{small}\begin{singlespace}\begin{minipage}[t]{5.5in}\rule{5.5in}{1pt}\vspace{\baselineskip}\begin{verbatim}keep_looking = ((aa == bb)
               || ((aa == 2) && (bb == 0))
               || ((aa == 0) && (bb == 2)));
if (keep_looking)
  continue;
if (aa == 2)
  aa = 0;
if (bb == 2)
  bb = 0;
return ((aa<bb) ? -1 : 1);
\end{verbatim}
\rule{5.5in}{1pt}\end{minipage}\end{singlespace}\end{small}\end{center}\vspace{-11pt}


\label{figure:cmppt-optimized}
\end{figure}
}

{\newpage
\clearpage
\samepage \begin{figure}\begin{center}\begin{small}\begin{singlespace}\begin{minipage}[t]{5.5in}\rule{5.5in}{1pt}\vspace{\baselineskip}\etc/
\begin{verbatim}qif (EQUALITY_FIRST) {
  keep_looking = ((aa == bb)
                  || ((aa == 2) && (bb == 0))
                  || ((aa == 0) && (bb == 2)));
}
qelse qif(AA_EQUALS_TWO_FIRST) {
  keep_looking = (((aa == 2) && (bb == 0))
                  || (aa == bb)
                  || ((aa == 0) && (bb == 2)));
}
qelse qif(BB_EQUALS_TWO_FIRST) {
  keep_looking = (((bb == 2) && (aa == 0))
                  || ((aa == 2) && (bb == 0))
                  || (aa == bb));
}
\end{verbatim}
\etc/
\vspace{7pt}
\rule{5.5in}{1pt}\end{minipage}\end{singlespace}\end{small}\end{center}\vspace{-11pt}


\label{figure:cmppt-quasi}
\end{figure}
}

{\newpage
\clearpage
\samepage \begin{table}\begin{center}
\begin{tabular}{|l|c|r|r|}
\hline
Version & Instrumented? & Inner loop cycles & Program user time \\ 
\hline
\hline
Original {\tt cmppt()} & N/A & N/A & 19.95 sec. \\ 
\hline
\hline
EQUALITY_FIRST      & Yes & 2828759078 & 136.83 sec. \\ 
EQUALITY_FIRST      & No  & N/A & 18.53 sec. \\ 
AA_EQUALS_TWO_FIRST & Yes & 3122155670 & 139.80 sec. \\ 
AA_EQUALS_TWO_FIRST & No  & N/A & 20.19 sec. \\ 
BB_EQUALS_TWO_FIRST & Yes & 3154715805 & 140.21 sec. \\ 
BB_EQUALS_TWO_FIRST & No  & N/A & 20.08 sec. \\ 
\hline
\end{tabular}
\end{center}

\label{table:cmppt-versions}
\end{table}
}

\stepcounter{paragraph}
\stepcounter{section}
\stepcounter{subsection}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$N^2$}\lthtmltypeout{latex2htmlSize :tex2htmlwrapinline2224: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$N^2$}\lthtmltypeout{latex2htmlSize :tex2htmlwrapinline2230: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{figure}\begin{center}\begin{small}\begin{singlespace}\begin{minipage}[t]{5.5in}\rule{5.5in}{1pt}\vspace{\baselineskip}\begin{verbatim}extern Matrix A;
Matrix AA = Matrix_copy(A);
Permutations P;

if (is_tridiagonal(A))                       /* O(N^2) */
  LU_decompose_tridiagonal(AA,P);            /* O(N) */
else if (is_band_diagonal(A))                /* O(N^2) */
  LU_decompose_band_diagonal(AA,P);          /* O(f(N, band width)) */
else if (is_bordered_band_diagonal(A))       /* O(N^2) */
  LU_decompose_bordered_band_diagonal(AA,P); /* O(f(N, band width,
                                                    border width) */
else if (is_triangular(A))                   /* O(N^2) */
  LU_decompose(AA,P);                        /* O(N^3), smaller constant */
else
  LU_decompose_general(AA,P);                /* O(N^3) */
}
\end{verbatim}
\rule{5.5in}{1pt}\end{minipage}\end{singlespace}\end{small}\end{center}\vspace{-11pt}


\label{figure:matrix-test}
\end{figure}
}

{\newpage
\clearpage
\samepage \begin{figure}\begin{center}\begin{small}\begin{singlespace}\begin{minipage}[t]{5.5in}\rule{5.5in}{1pt}\vspace{\baselineskip}\begin{verbatim}qif(MATRIX_OFTEN_TRIDIAGONAL) {
  if (is_tridiagonal(AA))
    LU_decompose_tridiagonal(AA,P);
  else LU_decompose_general(AA,P);
}
qelse qif(MATRIX_OFTEN_BAND_DIAGONAL) {
  if (is_band_diagonal(AA))
    LU_decompose_band_diagonal(AA,P);
  else LU_decompose_general(AA,P);
}
qelse qif(MATRIX_OFTEN_BORDERED_BAND_DIAGONAL) {
  if (is_bordered_band_diagonal(AA))
    LU_decompose_bordered_band_diagonal(AA,P);
  else LU_decompose_general(AA,P);
}
qelse qif(MATRIX_OFTEN_TRIANGULAR) {
  if (is_triangular(AA))
    LU_decompose_triangular(AA,P);
  else LU_decompose_general(AA,P);
}
qelse {
  LU_decompose_general(AA,&P);
}
\end{verbatim}
\rule{5.5in}{1pt}\end{minipage}\end{singlespace}\end{small}\end{center}\vspace{-11pt}


\label{figure:matrix-qif-test}
\end{figure}
}

\stepcounter{subsection}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$N \times N$}\lthtmltypeout{latex2htmlSize :tex2htmlwrapinline2232: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$B
\times B$}\lthtmltypeout{latex2htmlSize :tex2htmlwrapinline2234: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$B \times B$}\lthtmltypeout{latex2htmlSize :tex2htmlwrapinline2236: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$2N^3+N^2$}\lthtmltypeout{latex2htmlSize :tex2htmlwrapinline2244: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$B \times B$}\lthtmltypeout{latex2htmlSize :tex2htmlwrapinline2248: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$2N^3/B+N^2$}\lthtmltypeout{latex2htmlSize :tex2htmlwrapinline2256: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$B
\times B$}\lthtmltypeout{latex2htmlSize :tex2htmlwrapinline2262: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{figure}\begin{center}\begin{small}\begin{singlespace}\begin{minipage}[t]{5.5in}\rule{5.5in}{1pt}\vspace{\baselineskip}\begin{verbatim}#define MIN(a,b) ((a)<(b) ? (a) : (b))
#define ELEMENT(a,b,c) (*(a+(b*N)+c))

ELEMENT_TYPE *BlockedMultiply(ELEMENT_TYPE *X, ELEMENT_TYPE *Y,
                              ELEMENT_TYPE *Z, int N, int B)
{
  int kk, jj, i, j, k;
  ELEMENT_TYPE r;

  /* Allow me to do base-1 addressing instead of base-0 addressing;
     This is a similar trick to what Numerical Recipes does. */
  X = X-(N+1);
  Y = Y-(N+1);
  Z = Z-(N+1);

  for (kk=1; kk<=N; kk+=B)
    for (jj=1; jj<=N; jj+=B)
      for (i=1; i<=N; i++)
        for (k=kk; k<=MIN((kk+B-1),(N)); k++)
          {
            r = ELEMENT(X,i,k);
            for (j=jj; j<=MIN((jj+B-1),(N)); j++)
              ELEMENT(Z,i,j) += r*ELEMENT(Y,k,j);
            /* gcc -O is capable of hoisting unnecessary calculations
               out of this innermost loop */
          }
  return (Z+(N+1));
}
\end{verbatim}
{\rule{5.5in}{1pt}\end{minipage}\end{singlespace}\end{small}\end{center}\vspace{-11pt}}

\label{figure:blocked-mult-impl}
\end{figure}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$256*256$}\lthtmltypeout{latex2htmlSize :tex2htmlwrapinline2268: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{table}\begin{center}
\begin{tabular}{|c|r|r|||c|r|r|}
\hline
Data & Block size & Cycles ($10^9$) & Data & Block size & Cycles ($10^9$) \\ 
\hline
\hline
Double  &   1     &    25.076         & Integer &   1     &       22.929  \\ 
\hline
Double  &   2     &    10.769         & Integer &   2     &        9.382  \\ 
\hline
Double  &   3     &     8.086         & Integer &   3     &        6.693  \\ 
\hline
Double  &   4     &     5.639         & Integer &   4     &        5.189  \\ 
\hline
Double  &   5     &     5.814         & Integer &   5     &        4.920  \\ 
\hline
Double  &   6     &     5.198         & Integer &   6     &        4.444  \\ 
\hline
Double  &   7     &     5.026         & Integer &   7     &        4.247  \\ 
\hline
Double  &   8     &     4.482         & Integer &   8     &        3.763  \\ 
\hline
Double  &  16     &     3.993         & Integer &  16     &        3.359  \\ 
\hline
Double  &  32     &     3.858         & Integer &  32     &        3.161  \\ 
\hline
Double  &  64     &     3.871         & Integer &  64     &        3.133  \\ 
\hline
Double  & 128     &     3.929         & Integer & 128     &        3.143  \\ 
\hline
Double  & 256     &     3.988         & Integer & 256     &        3.149  \\ 
\hline
Double  & 512     &     3.960         & Integer & 512     &        3.149  \\ 
\hline
\end{tabular}
\end{center}

\label{table:matrix-512}
\end{table}
}

{\newpage
\clearpage
\samepage \begin{table}\begin{center}
\begin{tabular}{|r|r|r|r|}
\hline
Block size & Cycles ($10^9$) & User time (sec.) & Page faults \\ 
\hline
\hline
   1       &    415.661      &       4535.27    &        7391 \\ 
\hline
   2       &    166.012      &       1741.84    &        8591 \\ 
\hline
   3       &    129.969      &       1174.76    &       26430 \\ 
\hline
   4       &     88.316      &        880.94    &        8692 \\ 
\hline
   5       &    112.771      &        819.91    &       40829 \\ 
\hline
   6       &     90.070      &        743.83    &       26271 \\ 
\hline
   7       &    104.778      &        708.32    &       42682 \\ 
\hline
   8       &     66.948      &        638.46    &        8718 \\ 
\hline
  16       &     61.818      &        575.68    &        9216 \\ 
\hline
  32       &     58.378      &        542.88    &        8967 \\ 
\hline
  64       &     54.341      &        528.72    &        8248 \\ 
\hline
 128       &     53.014      &        527.25    &        8625 \\ 
\hline
 256       &     60.773      &        526.70    &       17372 \\ 
\hline
 320       &     91.283      &        533.96    &       50052 \\ 
\hline
 640       &     60.963      &        547.51    &       15121 \\ 
\hline
1280       &     57.006      &        573.51    &        6582 \\ 
\hline
\end{tabular}
\end{center}

\label{table:matrix-1280}
\end{table}
}

\stepcounter{chapter}
\stepcounter{section}
\stepcounter{section}
\stepcounter{paragraph}
\stepcounter{paragraph}
\stepcounter{paragraph}
\stepcounter{section}
\stepcounter{subsection}
\stepcounter{paragraph}
\stepcounter{paragraph}
\stepcounter{subsection}
\stepcounter{paragraph}
\stepcounter{paragraph}
\stepcounter{paragraph}
\stepcounter{subsection}
\stepcounter{paragraph}
\stepcounter{paragraph}
\stepcounter{paragraph}
\appendix
\stepcounter{chapter}
\stepcounter{section}
{\newpage
\clearpage
\samepage \begin{figure}\begin{center}\begin{small}\begin{singlespace}\begin{minipage}[t]{5.5in}\rule{5.5in}{1pt}\vspace{\baselineskip}\begin{verbatim}#include <stdio.h>
#include <stdlib.h>

int abs(int i) {
  if (i<0)
    return -i;
  else
    return i;
}

int main(int argc, char *argv[]) {
  signed int loop;
  for (loop = -10; loop <= 0; loop++) printf("%d ", abs(loop));
}
\end{verbatim}
{\rule{5.5in}{1pt}\end{minipage}\end{singlespace}\end{small}\end{center}\vspace{-11pt}}

\label{figure:c}
\end{figure}
}

{\newpage
\clearpage
\samepage \begin{figure}\begin{center}\begin{small}\begin{singlespace}\begin{minipage}[t]{5.5in}\rule{5.5in}{1pt}\vspace{\baselineskip}\etc/
\begin{scriptsize}

\begin{verbatim}    PROC P:.abs
      Procedure symbol table: `abs'
        Types:
          <None>
        Symbols:
          s:p1: `i' var_sym with t:g17; param userdef 
          s:p2: `L1' label_sym 
        Definitions:
          <None>
        Annotations:
          ["enable_exceptions": "int_divide-by-0"]
        Parameters:
          abs.i
   1: mrk 
        ["line": 5 "countdown.c"]
   2: IF (Jumpto=L:abs.L1)
      IF HEADER
   3:   bfalse  e1, L:abs.L1
   4:     e1: sl t:g28 (i.32) abs.i, e2
   5:       e2: ldc t:g17 (i.32) 0
      IF THEN
   6:   mrk 
          ["line": 6 "countdown.c"]
   7:   ret  e1
   8:     e1: neg t:g17 (i.32) abs.i
      IF ELSE
   9:   mrk 
          ["line": 8 "countdown.c"]
  10:   ret  abs.i
      IF END
    PROC END
\end{verbatim}
\end{scriptsize}
\etc/
\vspace{7pt}
{\rule{5.5in}{1pt}\end{minipage}\end{singlespace}\end{small}\end{center}\vspace{-11pt}}

\label{figure:printsuif-abs}
\end{figure}
}

{\newpage
\clearpage
\samepage \begin{figure}\begin{center}\begin{small}\begin{singlespace}\begin{minipage}[t]{5.5in}\rule{5.5in}{1pt}\vspace{\baselineskip}\etc/
\begin{scriptsize}

\begin{verbatim}    PROC P:.main
      Procedure symbol table: `main'
        Types:
          <None>
        Symbols:
          s:p1: `argc' var_sym with t:g17; param userdef 
          s:p2: `argv' var_sym with t:g129; param userdef 
          s:p3: `loop' var_sym with t:g17; userdef 
          s:p4: `L1' label_sym 
          s:p5: `L2' label_sym 
        Definitions:
          <None>
        Annotations:
          ["enable_exceptions": "int_divide-by-0"]
        Parameters:
          main.argc
          main.argv
   1: mrk 
        ["line": 13 "countdown.c"]
   2: FOR (Index=main.loop Test=SLTE Cont=L:main.L1 Brk=L:main.L2)
      FOR LB
  24:   ldc t:g17 (i.32) -10
      FOR UB
  16:   ldc t:g17 (i.32) 0
      FOR STEP
  18:   ldc t:g17 (i.32) 1
      FOR LANDING PAD
      FOR BODY
   3:   mrk 
          ["line": 13 "countdown.c"]
   4:   mrk 
          ["line": 13 "countdown.c"]
   5:   mrk 
          ["line": 13 "countdown.c"]
   6:   cal t:g17 (i.32) <nullop> = e1(e2, e3)
   7:     e1: ldc t:g211 (p.32) <P:.printf,0>
  23:     e2: ldc t:g46 (p.32) <.__tmp_string_0,0>
  10:     e3: cal t:g17 (i.32) e4(main.loop)
  11:       e4: ldc t:g214 (p.32) <P:.abs,0>
      FOR END
  19: mrk 
        ["line": 13 "countdown.c"]
  20: mrk 
        ["line": 14 "countdown.c"]
  21: ret  e1
  22:   e1: ldc t:g17 (i.32) 0
    PROC END
\end{verbatim}
\end{scriptsize}
\etc/
\vspace{7pt}
{\rule{5.5in}{1pt}\end{minipage}\end{singlespace}\end{small}\end{center}\vspace{-11pt}}

\label{figure:printsuif-main}
\end{figure}
}

{\newpage
\clearpage
\samepage \begin{figure}\begin{center}\begin{small}\begin{singlespace}\begin{minipage}[t]{5.5in}\rule{5.5in}{1pt}\vspace{\baselineskip}\etc/
\begin{scriptsize}

\begin{verbatim}extern int abs1(int);
extern int main(int, char **);
extern int printf();

extern int abs1(int i)
  {
    if (i < 0)
      {
        return -i;
      }
    else
      {
        return i;
      }
  }

extern int main(int argc, char **argv)
  {
    int loop;

    for (loop = -10; loop <= 0; loop++)
      {
        printf("%d ", abs1(loop));
      }
    return 0;
  }
\end{verbatim}
\end{scriptsize}
\etc/
\vspace{7pt}
{\rule{5.5in}{1pt}\end{minipage}\end{singlespace}\end{small}\end{center}\vspace{-11pt}}

\label{figure:s2c}
\end{figure}
}

\stepcounter{section}
\stepcounter{paragraph}
\stepcounter{paragraph}
\stepcounter{paragraph}
\stepcounter{paragraph}
\stepcounter{paragraph}
\stepcounter{chapter}
\stepcounter{section}
\stepcounter{section}
\stepcounter{section}
\stepcounter{section}
{\newpage
\clearpage
\samepage \begin{figure}\begin{center}\begin{small}\begin{singlespace}\begin{minipage}[t]{5.5in}\rule{5.5in}{1pt}\vspace{\baselineskip}\begin{scriptsize}

\begin{verbatim}#include <stdio.h>
#include <stdlib.h>

#define RDTSC ".hword 0x310F" /* db 0Fh 31h */

INLINE int function(int fiddle)
{
  fiddle++;
  return (fiddle*2);
}

int main(int argc, char *argv[])
{
  register int eax asm ("%eax");
  register int edx asm ("%edx");
  int start_hi, start_lo, finish_hi, finish_lo;
  int dummy_start_hi, dummy_start_lo, dummy_finish_hi, dummy_finish_lo;
  unsigned long long int cycles, dummy_cycles;

  asm volatile (RDTSC);
  start_hi = edx; start_lo = eax;

#ifndef DO_NOTHING
  #ifdef TIME_PROFILING_CODE
    /* Duplicate all the code which would be wrapped around
       something which I wanted to profile */
    asm volatile (RDTSC);
    dummy_start_hi = edx; dummy_start_lo = eax;
    /* CODE WHICH I WANTED TO PROFILE WOULD GO HERE */
    asm volatile (RDTSC);
    dummy_finish_hi = edx; dummy_finish_lo = eax;
    dummy_cycles = ((dummy_finish_hi-dummy_start_hi)*(1<<31)
  		  + (dummy_finish_lo-dummy_start_lo));
  #else
      {
        int i = 0;
    #ifndef JUST_ONCE
    #define ITERATIONS 1000
        for (; i<ITERATIONS; i++)
    #endif
          function(i);
    
      }
  #endif
#endif

  asm volatile (RDTSC);
  finish_hi = edx; finish_lo = eax;

  cycles = ((finish_hi-start_hi)*(1<<31) + (finish_lo-start_lo));
  printf("Time elapsed: %i (%X:%X) cycles, %.f nanoseconds.\n",
	 (int) cycles,
	 (finish_hi-start_hi), (finish_lo-start_lo),
	 cycles / 90000000.0 * 1000000000.0);
  /* Prevent gcc from optimizing dummy_* variable operations away altogether */
  if (dummy_cycles == 0) return 1;
}
\end{verbatim}
\end{scriptsize}
{\rule{5.5in}{1pt}\end{minipage}\end{singlespace}\end{small}\end{center}\vspace{-11pt}}

\label{figure:test-rdtsc}
\end{figure}
}

\stepcounter{chapter}
\stepcounter{paragraph}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$N^2$}\lthtmltypeout{latex2htmlSize :tex2htmlwrapinline2298: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{singlespace}\begin{minipage}[t]{5.5in}\rule{5.5in}{1pt}\vspace{\baselineskip}\begin{verbatim}qif(FLATTEN_FIRST)
  {
    initialize_truth_table_copy();
    qsort_using_copy(..., cmppt_using_copy);
  }
qelse
  {
    qsort(..., cmppt);
  }
\end{verbatim}
\rule{5.5in}{1pt}\end{minipage}\end{singlespace}
}

\stepcounter{paragraph}
\stepcounter{chapter}
\stepcounter{section}
\stepcounter{section}
\stepcounter{section}
\stepcounter{section}
\stepcounter{section}
\stepcounter{section}
{\newpage
\clearpage
\samepage \begin{singlespace}\bibitem[A94]{A94}
Michael Abrash, {\it Zen of Code Optimization}.  Coriolis Group Books: 1994.

\bibitem[B95]{B95}
Jeremy Brown, ``Feedback-Directed Specialization of C''.  Master of
engineering thesis, Massachusetts Institute of Technology, EECS
Department, June 1995.

\bibitem[BDE94]{BDE94}
Jeremy Brown, Andre DeHon, Ian Eslick, et al., ``The Clever Compiler:
Proposal for a First-Cut Smart Compiler.''  Transit Note 101, MIT
Artificial Intelligence Laboratory, January 1994.

\bibitem[C+91]{C+91}
Cmelik, et al., ``An Analysis of the MIPS and SPARC Instruction Set
Utilization on the SPEC Benchmarks.''  Appeared in {\it Proceedings of
the 4$^{\rm TH}$
 international conference on Architectural support
for programming languages and operating systems}, pg.\ 290--302, 1991.

%




%




\bibitem[CGL95]{CGL95}
Brad Calder, Dirk Grunwald, \& Donald Lindsay, ``Corpus-based Static
Branch Prediction.''  To appear in {\it Proceedings of the ACM SIGPLAN
Conference on Programming Language Design and Implementation
(PLDI'95)}, June 1995.

%
\bibitem[CLR90]{CLR90}
Thomas H.\ Cormen, Charles E.\ Leiserson, \& Ronald L.\ Rivest, {\it
Algorithms}.  MIT Press, Cambridge, Mass., 1990.

\bibitem[CMCH91]{CMCH91}
Pohua P.\ Chang, Scott A.\ Mahlke, William Y.\ Chen, \& Wen-Mei Hwu,
``Profile-guided Automatic Inline Expansion for C Programs''.
Appeared in {\it Software --- Practice and Experience}, Vol.\ 22(5),
May 1992, pg.\ 349--369.

%





\bibitem[CSW94]{CSW94}
Yin Chan, Ashok Sudarsanam, \& Andrew Wolfe, ``The Effect of
Compiler-Flag Tuning on SPEC Benchmark Performance.''  Appeared in
{\it Computer Architecture News}, 22:4, Sept. 1994, pg.\ 60--70.
%







\bibitem[D94a]{D94a}
Andre DeHon, ``DPGA-Coupled Microprocessors: Commodity ICs for the
Early 21st Century.''  Transit Note 100, MIT Artificial Intelligence
Laboratory, January 1994.

\bibitem[D94b]{D94b}
Andre DeHon, ``A Proposal for Alternative Code: a
quasistatic-if-then-else and quasistatic variables.'' Transit Note 110
(working draft), MIT Artificial Intelligence Laboratory, July 1994.

\bibitem[DBE+94]{DBE+94}
Andre DeHon, Jeremy Brown, Ian Eslick, et al., ``Global Cooperative
Computing.''  Transit Note 111, MIT Artificial Intelligence
Laboratory, Sept.\ 1994.

\bibitem[DC94]{DC94}
Jeffrey Dean \& Craig Chambers, ``Towards Better Inlining Decisions
Using Inlining Trials.''  Presented at {\it 1994 ACM Conference on
LISP and Functional Programming}, Orlando, Florida; June 1994.

\bibitem[DCG95]{DCG95}
Jeffrey Dean, Craig Chambers, \& David Grove, ``Selective
Specialization for Object-Oriented Languages.''  To appear in {\it
SIGPLAN'95: Conference on Programming Language Design and
Implementation (PLDI'95)}, June 1995.

\bibitem[DE94]{DE94}
Andre DeHon \& Ian Eslick, ``Computational Quasistatics.'' Transit
Note 103, MIT Artificial Intelligence Laboratory, March 1994.

\bibitem[EP93]{EP93}
Dawson Engler \& Todd Proebsting, ``DCG: An Efficient, Retargetable
Dynamic Code Generation System.''  November 1993.  (Contact: {\tt
todd@cs.arizona.edu}, {\tt engler@lcs.mit.edu}.)

\bibitem[FF92]{FF92}
Fisher and Freudenberger, ``Predicting Conditional Branch Directions
from Previous Runs of a Program.''  Appeared in {\it Proceedings of the
4$^{\rm TH}$
 international conference on Architectural support for
programming languages and operating systems}, pg.\ 85--95, 1992.

\bibitem[FH94]{FH94}
Chris Fraser \& David Hanson, {\it A Retargetable C Compiler: Design
and Implementation}.  Benjamin/Cummings: 1994.
%









%




\bibitem[G93]{G93}
Gray, ``SPEC: A Five Year Retrospective.''  Appeared in {\it SPEC
Newsletter}, 5:4, December 1993.

\bibitem[G95]{G95}
Greg McLaren, ``QProf: A Scalable Profiler for the Q Back End.''
Master of engineering thesis, Massachusetts Institute of Technology
EECS Department, January 1995.

%




\bibitem[GKM82]{GKM82}
Susan L.\ Graham, Peter B.\ Kessler \& Marshall K.\ McKusick, ``gprof:
a Call Graph Execution Profiler''.  Appeared in {\it Proceedings of
the SIGPLAN '82 Symposium on Compiler Construction}, pg.\ 120--126,
1982.

\bibitem[HU94]{HU94}
Urs Holze \& David Ungar, ``Optimizing Dynamically Dispatched Calls
with Run-Time Type Feedback.''  Appeared in {\it SIGPLAN Conference on
Programming Language Design and Implementation}, Orlando, Florida;
June 1994.

\bibitem[I94]{I94}
Intel Corporation, {\it Pentium Processor Family User's Manual Volume
3: Architecture and Programming Manual.}  Published 1994.

%





\bibitem[K71]{K71}
Donald E. Knuth, ``Empirical Study of FORTRAN Programs.'' {\it
Practice and Experience}, vol. 1, pg.\ 105--133.

\bibitem[K73]{K73}
D.\ E.\ Knuth, {\it The Art of Computer Programming, Volume 1:
Fundamental Algorithsm}.  Addison-Wesley, 1973.

\bibitem[K75]{K75}
D.\ E.\ Knuth, {\it The Art of Computer Programming, Volume 3: Sorting
and Searching}.  Addison-Wesley, 1975.

%










%
\bibitem[KR88]{KR88}
Brian W.\ Kernighan \& Dennis M.\ Ritchie, ``The C Programming
Language'', 2$^{\rm ND}$
 edition.  Prentice Hall, 1988.

\bibitem[LRW91]{LRW91}
Monica S.\ Lam, Edward E.\ Rothberg, \& Michael E.\ Wolf, ``The Cache
Performance and Optimizations of Blocked Algorithms''.  Appeared in
{\it 4$^{\rm TH}$
 International Conference on Architecture Support
for Programming Languages and Operating Systems (ASPLOS IV)}, Palo
Alta, California; April 9--11, 1991.

\bibitem[M94]{M94}
Terje Mathisen, ``Pentium Secrets.''  Appeared in {\it Byte}, July
1994, pg.\ 191--192.  See also the article posted to the Usenet {\tt
comp.arch} newsgroup in response to this article: ``From:
glew@ichips.intel.com (Andy Glew)'', ``Date: 16 Jul 1994 23:09:24
GMT'', ``\verb+Message-ID: <GLEW.94Jul9235235@pdx007.intel.com>+'',
``Subject: Re: "Pentium Secrets"''.

\bibitem[MGA95]{MGA95}
Margaret Martonosi, Anoop Gupta, \& Thomas E.\ Anderson, ``Tuning
Memory Performance of Sequential and Parallel Programs.''  Appeared in
{\it IEEE Computer}, April 1995, pg.\ 32--40.

\bibitem[OSF93]{OSF93}
Open Software Foundation Research Institute, {\it ANDF Technology
Collected Papers}.  Volumes 1--4, January/March/June/December 1993.
See also WWW URL {\sf http://riwww.osg.org:8001/andf/index.html} for
additional Architecture-Neutral Distribution Format information.

\bibitem[PFTV88]{PFTV88}
William H.\ Press, Brian P.\ Flannery, Saul A.\ Teukolsky, \& William
T.\ Vetterling, {\it Numerical Recipes in C}.  Cambridge University
Press, 1988.

\bibitem[S91]{S91}
Alan Dain Samples, {\it Profile-driven Compilation}.  UC Berkeley,
Computer Science Division, Technical Report UCB/CSD 91/627, April
1991.

%











%




\bibitem[S94]{S94}
Richard M.\ Stallman, {\it Using and Porting GNU CC: Last updated 19
September 1994 for version 2.6.}  Free Software Foundation, 1994.
Available from {\sf ftp://prep.ai.mit.edu/pub/gnu/gcc-2.6.3.tar.gz}.

\bibitem[S95]{S95}
Jonathan Schilling, ``Dynamically-Valued Constants: An Underused
Language feature.''  Appeared in {\it ACM SIGPLAN Notices}, Volume 30,
No.\ 4, April 1995, pg.\ 13--20.

%



\bibitem[SW92]{SW92}
Amitabh Srivastava \& David W.\ Wall, ``A Practical System for
Intermodule Code Optimization at Link-Time.''  DEC Western Research
Laboratory, WRL Research Report 92/6, December 1992.

\bibitem[W90]{W90}
David W.\ Wall, ``Predicting Program Behavior Using Real or Estimated
Profiles.''  DEC Western Research Laboratory WRL Technical Note TN-18,
December 1990.

%



\bibitem[WFW+94]{WFW+94}
Robert P.\ Wilson, Robert S.\ French, Christopher S.\ Wilson, et al.,
``SUIF: An Infrastructure for Research on Parallelizing and Optimizing
Compilers.''  Computer Systems Lab, Stanford University, 1994.
Available at the WWW URL {\sf
http://suif.stanford.edu/suif/suif-overview/suif-overview.html}.

%




\end{singlespace}
}

\stepcounter{chapter}

\end{document}
