\documentstyle[11pt,simplemargins]{article}
\setallmargins{1in}
% no page numbers
\pagestyle{empty}
% counter for page numbers
\newcounter{pg}
\setcounter{pg}{2}

% DEFINE THE PROBLEM SET NUMBER
\def\psnum{4}

% DEFINE THE DUE DATE
\def\due{December 2, 1991}

% title command
\newcommand{\mytitle}{{\large\noindent 6.035 Computer Language
Engineering \hfill{} Juliet Bourne \\ 
Homework \#\psnum \hfill{} \due \\}
\vspace{-.43in}
\begin{center} \rule{6.5in}{.25mm} \end{center}}
% newpage setup command 
\newcommand{\mypage}[1]{\newpage{\large\noindent 6.035 Computer Language
Engineering \hfill{} Juliet Bourne \\
Homework \#\psnum \hfill{} \due \\}
\vspace{-.43in}
\begin{center} \rule{6.5in}{.25mm} \end{center}}
%\newcommand{\mynewpage}{\newpage\noindent
%{\large 6.035 \hfill{} Juliet Bourne \\
%Problem Set \psnum \hfill{} {\bf Page \thepg} \\}
%\vspace{-.6in}
%\begin{center}
%\rule{6in}{.25mm}
%\end{center}
%\addtocounter{pg}{1}}
% problem command
\newcommand{\prob}[1]{\noindent{\fbox{\large\bf Problem #1}}\vspace{.25in}}
% subproblem command
\newcommand{\subprob}[1]{\vspace{.15in} \noindent{\large\bf #1.}}
% equations commands
\newcommand{\beq}{\vspace*{-.3in}\begin{eqnarray*}}
\newcommand{\eeq}{\end{eqnarray*}}

\newcommand{\PSbox}[3]{\mbox{\rule{0in}{#3}\special{psfile=#1}\hspace{#2}}}

\begin{document}

\mytitle

\prob{1}

\subprob{a} First basic block, with comments:

\begin{verbatim}
start:  movl $18, r1            # r1 contains 18
        movl $8, r2             # r2 contains 8
        divl3 r2, r1, r3        # r3 contains 2.25
        mull3 r2, r3, r4        # r4 contains 18
        cmpl r1, r4             # 18=18?
        jeql exit               # always taken!
\end{verbatim}

Second basic block, with comments:

\begin{verbatim}
        divl3 r2, r1, r5        # r5 contains 2.25
        mull3 r5, r2, r6        # r6 containts 18
        subl3 r6, r1, r7        # r7 contains 0
        movl r2, r1             # r1 contains 8
        movl r7, r2             # r2 contains 0
        divl3 r2, r1, r3        # 8 / 0 ==> division by zero!!
        mull3 r2, r3, r4        # ??
        cmpl r1, r4             # ??
        jeql exit
\end{verbatim}

\subprob{b} As shown in the comments above, the first block results in
the jump to ``exit'' always being taken. So, the first block can be
reduced to:

\begin{verbatim}
start:  movl $18, r1
        movl $8, r2
        movl $2.25, r3
        movl $18, r4
        jbr exit
\end{verbatim}

\noindent or even just: 

\begin{verbatim}
start:  jbr exit
\end{verbatim}

Since the first block always jumps, the second block is never reached.
And even if it were reached, it would be reduced to either a static
error for division by zero or a piece of code that would jump
unconditionally to a ``Division by zero'' label that would print the
error message and terminate the program.

\subprob{c} So, the code fragment would be (in the simplest case):

\begin{verbatim}
start:  jbr exit
        jbr div0
\end{verbatim}

\subprob{d} What's left to do?

\mypage

\prob{2}

\vspace*{-.35in}
\subprob{a} The DAG: 

\PSbox{/mit/jcbourne/Psets/6035/dag.ps voffset=-24}{4.5in}{4in}

\subprob{b} Sequence of instructions resulting from a topological sort
of the above DAG:

\vspace*{-.075in}
\begin{verbatim}
        movl *n(fp), r0
        movl m(fp), r1
        movl *n(fp), r6        # not needed, r0 = r6
        movl m(fp), r7         # not needed, r1 = r7
        mull3 r1, $4, r2 
        mull3 r7, $4, r8       # not needed, r2 = r8
        addl3 r0, r2, r3
        movl (r3), r4
        addl3 r4, $1, r5
        addl3 r6, r8, r9       # change registers
        movl r5, (r9)          # change registers
\end{verbatim}

\noindent or, as the comments suggest, with a bit of common
subexpression elimination: 

\vspace*{-.075in}
\begin{verbatim}
        movl *n(fp), r0
        movl m(fp), r1
        mull3 r1, $4, r2
        addl3 r0, r2, r3
        movl (r3), r4
        addl3 r4, $1, r5
        addl3 r0, r2, r6
        movl r5, (r6)
\end{verbatim}

\mypage

\prob{3}

\begin{verbatim}
   --------------------------------------------------
      Load/Store   |   Arithmetic  |   Branching
   --------------------------------------------------
         noop      | r2 <- r0 + r1 |     noop
   --------------------------------------------------
   r3 <- load (r2) |      noop     |     noop         # use new r2 value
   --------------------------------------------------
         noop      |      noop     | jcond (r3<10) L1 # use new r3 value
   --------------------------------------------------
         noop      | r4 <- r3 + 10 |    jump L2       # unconditional jump
   --------------------------------------------------
L1:      noop      | r4 <- 10 - r3 |     noop         # only 1 op in L1
   --------------------------------------------------
L2: store (r2), r4 | r2 <- r0 + 5  |     noop         # reg read before write
   --------------------------------------------------
         noop      | r1 <- r1 + 1  |     noop
   --------------------------------------------------
         noop      | r5 <- r5 + 1  | jcond (r1>r6) L  # r1,r6 already computed
   --------------------------------------------------
\end{verbatim}

\end{document}

