\documentclass[12pt]{article}
\usepackage[utf8]{inputenc}
\usepackage{listings}
\usepackage{inconsolata}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage[margin=1in]{geometry}
\usepackage{algorithmicx}
\usepackage{algpseudocode}
\usepackage{amsmath}
\usepackage{tikz}
\usepackage{mathtools}
\usepackage{proof}
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{hyperref}

\definecolor{color1}{HTML}{FFAABB}
\definecolor{color2}{HTML}{EEDD66}
\definecolor{color3}{HTML}{77AADD}
\definecolor{color4}{HTML}{EE6C6C}
\definecolor{color5}{HTML}{99DDFF}
\definecolor{color6}{HTML}{44BB99}
\definecolor{color7}{HTML}{BBCC33}
\definecolor{color8}{HTML}{AAAA00}
\definecolor{color9}{HTML}{DDDDDD}
            
\usetikzlibrary{positioning}

\algrenewcommand{\algorithmicforall}{\textbf{for each}}

\newcommand*{\lineref}[1]{$\langle$line #1$\rangle$}
\newcommand*{\objref}[1]{$\langle$object \texttt{#1}$\rangle$}
\newcommand*{\voidref}[1]{\texttt{void}}
\newcommand*{\so}{\textit{so}}
\newcommand*{\Int}{\mathrm{Int}}

\lstdefinelanguage{Cool}{
    morekeywords = {if,fi,pool,loop,while,else,class,inherits,case,in,of,esac,let,new,try,catch,yrt,throw},
    morekeywords = [2]{Int,Object,Value,MulOp,AddOp,Stack,Main,IO,SELF_TYPE},
    morecomment=[l]{--},
    morecomment=[n]{(*}{*)},
    morestring=[b]{"},
    literate={<-}{$\gets{}$}{2}{<=}{$\le{}$}{2}{=>}{$\Rightarrow{}$}{2},
}
\lstdefinestyle{mystyle}{
    numbers=left,numberstyle=\tiny,numbersep=10pt,
    commentstyle=\color{gray},
    keywordstyle=\bfseries,
    keywordstyle={[2]\color{BlueViolet}},
    stringstyle=\color{Mahogany},
    numberstyle=\color{darkgray},
}
\lstset{
    basicstyle=\ttfamily\small,
    tabsize=2,
    style=mystyle,
}

\title{CS143 Written Assignment 4}
\author{Your Name -- SUNet ID}
\date{Due: June 3rd, 2025 EOD}

\begin{document}
\maketitle

\newpage

\section*{Problem 1. Programming in Assembly}

\

The secret string is:

\

\

Your program:

\begin{verbatim}
    (Copy your program here)    
\end{verbatim}

\newpage

\section*{Problem 2. Single Static Assignment (SSA) Form}

\ 

\textbf{(Task 2.A)}

    \begin{center}
        \begin{tikzpicture}[bb/.style={text width=1.5in, draw, align=center}, node distance=0.4cm]
            \node[bb] (entry) {\textsc{Entry}};
            \node[bb,below=of entry] (b1) {$\begin{aligned}
                x &\coloneqq 1 \\
                y &\coloneqq 2 \\
                x &\coloneqq x + y \\
                y &\coloneqq y - x \\
                z &\coloneqq x + y \\
            \end{aligned}$ \\
            \vspace{0.3em}
            \textbf{if} 
            $x > z$
            \textbf{goto} B2 \\
            \textbf{else goto} B3};
            \node[bb,below left=of b1] (b2) {$\begin{aligned}
                x &\coloneqq x + y \\
                z &\coloneqq z + x \\
            \end{aligned}$ };
            \node[bb,below right=of b1] (b3) {$\begin{aligned}
                y &\coloneqq y + z \\
                z &\coloneqq x + y \\
            \end{aligned}$ \\
            \vspace{0.3em}
            \textbf{goto} B4};
            \node[bb,below=of b3] (b4) {$\begin{aligned}
                x &\coloneqq x + z\\
            \end{aligned}$ };
            \node[left=0pt of b1.north west, anchor=north east] {B1};
            \node[left=0pt of b2.north west, anchor=north east] {B2};
            \node[right=0pt of b3.north east, anchor=north west] {B3};
            \node[right=0pt of b4.north east, anchor=north west] {B4};
            \draw[->,>=stealth] (entry) -- (b1);
            \draw[->,>=stealth] (b1.west) -| (b2.north);
            \draw[->,>=stealth] (b1.east) -| (b3.north);   
            \draw[->,>=stealth] (b3) -- (b4);
        \end{tikzpicture}
        \end{center}

\newpage

\textbf{(Task 2.B)}

\vspace{25em}

\textbf{(Task 2.C)}


\newpage

\textbf{(Task 2.D)}

\vspace{-2em}

\begin{center}
        \begin{tikzpicture}[bb/.style={text width=2.1in, draw, align=center}, bb2/.style={text width=1.5in, draw, align=center}, node distance=0.4cm]
            \node[bb] (entry) {\textsc{Entry}};
            \node[bb,below=of entry] (bz) {$\begin{aligned}
                \\
                \\
            \end{aligned}$ \\
            \textbf{goto} A};
            \node[bb,below=of bz] (b0) {$\begin{aligned}
                \\
                \\
                x &\coloneqq 0\\
                y &\coloneqq 0\\
            \end{aligned}$ \\
            \textbf{goto} B};
            \node[bb,below=of b0] (b1) {$\begin{aligned}
                \\
                \\
                x &\coloneqq x + 1 \\
            \end{aligned}$ \\
            \textbf{goto} C};
            \node[bb,below left=of b1] (b2) {$\begin{aligned}
                \\
                \\
                y &\coloneqq y + 1 \\
            \end{aligned}$\\
            $x < 5$ ? \textbf{goto} D : \textbf{goto} E};
            \node[bb2,below left=of b2] (b3) {$\begin{aligned}
                \\
                \\
                y &\coloneqq y + 1 \\
            \end{aligned}$ \\
            \textbf{goto} E};
            \node[bb,below right=of b3] (b4) {$\begin{aligned}
                \\
                \\
                y &\coloneqq x + y \\
            \end{aligned}$ \\
            $y < 5$ ? \textbf{goto} C : \textbf{goto} F};
            \node[bb,below right=of b4] (b5) {$\begin{aligned}
                \\
                \\
            \end{aligned}$\\
            $x < 10$ ? \textbf{goto} B : \textbf{goto} G};
            \node[bb,below=of b5] (b6) {$\begin{aligned}
                \\
                \\
            \end{aligned}$ \\
            \textbf{print}($y$) };
            \node[left=0pt of bz.north west, anchor=north east] {Z};
            \node[left=0pt of b0.north west, anchor=north east] {A};
            \node[left=0pt of b1.north west, anchor=north east] {B};
            \node[left=0pt of b2.north west, anchor=north east] {C};
            \node[left=0pt of b3.north west, anchor=north east] {D};
            \node[left=0pt of b4.north west, anchor=north east] {E};
            \node[left=0pt of b5.north west, anchor=north east] {F};
            \node[left=0pt of b6.north west, anchor=north east] {G};
            \draw[->,>=stealth] (entry) -- (bz);
            \draw[->,>=stealth] (bz) -- (b0);
            \draw[->,>=stealth] (b0) -- (b1);
            \draw[->,>=stealth] (b1.west) -| (b2.north);
            \draw[->,>=stealth] (b5.north) -- (b1.south);
            \draw[->,>=stealth] (b2.west) -| (b3.north);
            \draw[<->,>=stealth] (b2) -- (b4);
            \draw[->,>=stealth] (b3.south) |- (b4.west);
            \draw[->,>=stealth] (b4) |- (b5);
            \draw[->,>=stealth] (b5) -- (b6);
        \end{tikzpicture}
        \end{center}

\newpage

\textbf{(Task 2.E)}

\begin{enumerate}
    \item Every variable is assigned exactly once: \textcolor{red}{(your explanation here)}
    \item Every variable satisfies def-before-use requirement: \textcolor{red}{(your explanation here)}
    \item Every $\phi$ node satisfies def-before-use requirement: \textcolor{red}{(your explanation here)}
\end{enumerate}

\vspace{20em}

\textbf{(Task 2.F)}



\newpage

\textbf{(Task 2.G)}

\vspace{-2em}

\begin{center}
        \begin{tikzpicture}[bb/.style={text width=2.1in, draw, align=center}, bb2/.style={text width=1.5in, draw, align=center}, node distance=0.4cm]
            \node[bb] (entry) {\textsc{Entry}};
            \node[bb,below=of entry] (bz) {$\begin{aligned}
                \\
                \\
            \end{aligned}$ \\
            \textbf{goto} A};
            \node[bb,below=of bz] (b0) {$\begin{aligned}
                \\
                \\
                x &\coloneqq 0\\
                y &\coloneqq 0\\
            \end{aligned}$ \\
            \textbf{goto} B};
            \node[bb,below=of b0] (b1) {$\begin{aligned}
                \\
                \\
                x &\coloneqq x + 1 \\
            \end{aligned}$ \\
            \textbf{goto} C};
            \node[bb,below left=of b1] (b2) {$\begin{aligned}
                \\
                \\
                y &\coloneqq y + 1 \\
            \end{aligned}$\\
            $x < 5$ ? \textbf{goto} D : \textbf{goto} E};
            \node[bb2,below left=of b2] (b3) {$\begin{aligned}
                \\
                \\
                y &\coloneqq y + 1 \\
            \end{aligned}$ \\
            \textbf{goto} E};
            \node[bb,below right=of b3] (b4) {$\begin{aligned}
                \\
                \\
                y &\coloneqq x + y \\
            \end{aligned}$ \\
            $y < 5$ ? \textbf{goto} C : \textbf{goto} F};
            \node[bb,below right=of b4] (b5) {$\begin{aligned}
                \\
                \\
            \end{aligned}$\\
            $x < 10$ ? \textbf{goto} B : \textbf{goto} G};
            \node[bb,below=of b5] (b6) {$\begin{aligned}
                \\
                \\
            \end{aligned}$ \\
            \textbf{print}($y$) };
            \node[left=0pt of bz.north west, anchor=north east] {Z};
            \node[left=0pt of b0.north west, anchor=north east] {A};
            \node[left=0pt of b1.north west, anchor=north east] {B};
            \node[left=0pt of b2.north west, anchor=north east] {C};
            \node[left=0pt of b3.north west, anchor=north east] {D};
            \node[left=0pt of b4.north west, anchor=north east] {E};
            \node[left=0pt of b5.north west, anchor=north east] {F};
            \node[left=0pt of b6.north west, anchor=north east] {G};
            \draw[->,>=stealth] (entry) -- (bz);
            \draw[->,>=stealth] (bz) -- (b0);
            \draw[->,>=stealth] (b0) -- (b1);
            \draw[->,>=stealth] (b1.west) -| (b2.north);
            \draw[->,>=stealth] (b5.north) -- (b1.south);
            \draw[->,>=stealth] (b2.west) -| (b3.north);
            \draw[<->,>=stealth] (b2) -- (b4);
            \draw[->,>=stealth] (b3.south) |- (b4.west);
            \draw[->,>=stealth] (b4) |- (b5);
            \draw[->,>=stealth] (b5) -- (b6);
        \end{tikzpicture}
        \end{center}
        
\newpage

\section*{Problem 3. Liveness and Register Interference Graph}

\

\textbf{(Task 3.A)}

        \begin{center}
        \begin{tikzpicture}[bb/.style={text width=3in, draw}, node distance=0.4cm]
            \node[bb,align=center] (entry) {\textsc{Entry}($a, b$)};
            \node[bb,below=of entry] (b1) {\begin{tabular}{p{1.5in}l}
                                                                   & Live: \\
                $g \coloneqq a$                                    & Live: \\
                $f \coloneqq b$                                    & Live: \\
                \textbf{if} $g > f$ \textbf{goto} B2 \\
                \textbf{else goto} B3                              & Live: \\
            \end{tabular}};
            \node[bb,below left=0.4cm and 1cm of b1.south,anchor=north] (b2) {\begin{tabular}{p{1.5in}l}
                                                                   & Live: \\
                $g \coloneqq g + 2$                                & Live: \\
                $e \coloneqq g$                                    & Live: \\
                \textbf{goto} B4                                   & Live: 
            \end{tabular}};
            \node[bb,below right=0.4cm and 1cm of b1.south |- b2.south,anchor=north] (b3) {\begin{tabular}{p{1.5in}l}
                                                                   & Live: \\
                $e \coloneqq g$                                    & Live: \\
                \textbf{goto} B4                                   & Live: 
            \end{tabular}};
            \node[bb,below=of {b1.south |- b3.south}] (b4) {\begin{tabular}{p{1.5in}l}
                                                                   & Live: \\
                $e \coloneqq g$                                    & Live: \\
                $f \coloneqq f + 2$                                & Live: \\
                \textbf{if} $f < 10$ \textbf{goto} B4 \\
                \textbf{else goto} B5                              & Live: 
            \end{tabular}};
            \node[bb,below=of b4] (b5) {\begin{tabular}{p{1.5in}l}
                                                                   & Live: \\
                $c \coloneqq e * 32$                               & Live: \\
                $d \coloneqq f - b$                                & Live: \\
                \textbf{return} $(c, d)$                           & Live:
            \end{tabular}};
            \node[bb,below=of b5,align=center] (exit) {\textsc{Exit}};
            \node[left=0pt of b1.north west, anchor=north east] {B1};
            \node[left=0pt of b2.north west, anchor=north east] {B2};
            \node[right=0pt of b3.north east, anchor=north west] {B3};
            \node[left=0pt of b4.north west, anchor=north east] {B4};
            \node[left=0pt of b5.north west, anchor=north east] {B5};
            \draw[->,>=stealth] (entry) -- (b1);
            \draw[->,>=stealth] (b1.west) -- +(-0.75in,0) |- (b2.west);
            \draw[->,>=stealth] (b1.east) -- +( 0.75in,0) |- (b3.east);
            \draw[->,>=stealth] (b2.205) -- (b4.north -| b2.205);
            \draw[->,>=stealth] (b3.south) -- (b4.north -| b3.south);
            \draw[->,>=stealth] (b4) edge[loop right,in=10,out=-10,looseness=4] (b4);
            \draw[->,>=stealth] (b4) -- (b5);
            \draw[->,>=stealth] (b5) -- (exit);
        \end{tikzpicture}
        \end{center}

\newpage

\textbf{(Task 3.B)}

\

        \begin{centering} % sample interference graph
        \begin{tikzpicture}[every node/.style={minimum width=3em, circle, draw}]
            \node (a) at (51:2.1cm) {$a$};
            \node (b) at (0:1.8cm) {$b$};
            \node (c) at (300:1.6cm) {$c$};
            \node (d) at (235:1.8cm) {$d$};
            \node (e) at (187:2.0cm) {$e$};
            \node (f) at (145:2.4cm) {$f$};
            \node (g) at (100:2.2cm) {$g$};
            % you can draw line by:
            \draw (a) -- (b);
            \draw (a) -- (c);
            \draw (a) -- (d);
            \draw (d) -- (g);
            \draw (e) -- (g);
            \draw (f) -- (g);
        \end{tikzpicture}
        \end{centering}

    % sample list of edges
    \begin{verbatim}
    a -- b; 
    \end{verbatim}

    \

    \textbf{(Task 3.C)}

    \

    A minimum of \textcolor{red}{(your solution)} colors is needed.

    \
    
    \begin{centering} % sample interference graph
        \begin{tikzpicture}[every node/.style={minimum width=3em, circle, draw}]
            \definecolor{color1}{HTML}{FFAABB}
            \definecolor{color2}{HTML}{EEDD66}
            \definecolor{color3}{HTML}{77AADD}
            \definecolor{color4}{HTML}{EE6C6C}
            \definecolor{color5}{HTML}{99DDFF}
            \definecolor{color6}{HTML}{44BB99}
            \definecolor{color7}{HTML}{BBCC33}
            \definecolor{color8}{HTML}{AAAA00}
            \definecolor{color9}{HTML}{DDDDDD}
            % change fill=colorX as needed
            \node[fill=color1] (a) at (51:2.1cm) {$a$};
            \node[fill=color2] (b) at (0:1.8cm) {$b$};
            \node[fill=color3] (c) at (300:1.6cm) {$c$};
            \node[fill=color4] (d) at (235:1.8cm) {$d$};
            \node[fill=color5] (e) at (187:2.0cm) {$e$};
            \node[fill=color6] (f) at (145:2.4cm) {$f$};
            \node[fill=color7] (g) at (100:2.2cm) {$g$};
            % you can draw line by:
            \draw (a) -- (b);
            \draw (a) -- (c);
            \draw (a) -- (d);
            \draw (d) -- (g);
            \draw (e) -- (g);
            \draw (f) -- (g);
        \end{tikzpicture}
        \end{centering}
        
\end{document}