\section{Tests (Datenflussanalysen)}

Im Folgenden wird die Analyse als Beispiel für den Worklistalgorithmus \glqq Naiv\grqq\ angegeben.
%%Der Fixpunkt bei der Anwendung anderer Algorithmen ist gleich.
In diesem Beispiel wird davon ausgegangen, dass das erweiterte Java-Subset implementiert wurde.
Der CFG wird exemplarisch in Java-Code angegeben und nicht in Zwischencode wie in der implementierten Analyse.
%Hierbei wird angenommen, dass bei einer Verzweigung der linke Pfad bei einer wahren Bedingung und der rechte Pfad bei einer nicht erfüllten Bedingung genommen wird.


\subsection{Constant Folding}

Zu analysierender Code: \par

\begin{lstlisting}[frame=single]
int constFolding(int n) {
	int x = 6;
	int y = 2 * n;
	while (n > 0) {
		y = y - x;
		x = 3 * (x % 4);
		n = n - 1;
	}
	return y;
}
\end{lstlisting}

\par

\begin{figure}[H]

\centering
\begin{tikzpicture}[%
->,
shorten >=2pt,
>=stealth,
node distance=1cm,
noname/.style={%
	ellipse,
	minimum width=5em,
	minimum height=3em,
	draw
}
]

\node [draw] (1) {
\begin{lstlisting}[numbers=none]
In = {$n= \top, x = \perp, y = \perp$}
[*int x = 6;
int y = 2 * n;*]
Out = {$n= \top, x = \perp, y = \perp$}
\end{lstlisting}
};

\node [draw] (2) [below =of 1] {
\begin{lstlisting}[numbers=none]
In = {$n= \top, x = \perp, y = \perp$}
[*if (n > 0)*]
Out = {$n= \top, x = \perp, y = \perp$}
\end{lstlisting}
};

\node[draw] (3) [below left = 5 cm and 1 cm =of 2] {
\begin{lstlisting}[numbers=none]
In = {$n= \top, x = \perp, y = \perp$}
[*return y;*]
Out = {$n= \top, x = \perp, y = \perp$}
\end{lstlisting}
};

\node[draw] (4) [below right = 5 cm and 1 cm =of 2] {
\begin{lstlisting}[numbers=none]
In = {$n= \top, x = \perp, y = \perp$}
[*y = y - x;
x = 3 * (x % 4);
n = n - 1;*]
Out = {$n= \top, x = \perp, y = \perp$}
\end{lstlisting}
};

\path (1) edge node {} (2);
\path (2) edge [bend right=20pt] node {} (3);
\path (2) edge [bend right=20pt] node {} (4);
\path (4) edge [bend right=20pt] node {} (2);
\end{tikzpicture}

\caption{CFG im initialen Zustand der Constant-Folding-Analyse}
\end{figure}

\begin{figure}[H]
\centering
\begin{tikzpicture}[%
->,
shorten >=2pt,
>=stealth,
node distance= 1cm,
noname/.style={%
	ellipse,
	minimum width=5em,
	minimum height=3em,
	draw
}
]

\node [draw] (1) {
\begin{lstlisting}[numbers=none]
In = {$n= \top, x = \perp, y = \perp$}
[*int x = 6;
int y = 2 * n;*]
Out = {$n= \top, x = 6, y = \top$}
\end{lstlisting}
};

\node [draw] (2) [below =of 1] {
\begin{lstlisting}[numbers=none]
In = {$n= \top, x = \perp, y = \perp$}
[*if (n > 0)*]
Out = {$n= \top, x = \perp, y = \perp$}
\end{lstlisting}
};

\node[draw] (3) [below left  = 5 cm and 1 cm =of 2] {
\begin{lstlisting}[numbers=none]
In = {$n= \top, x = \perp, y = \perp$}
[*return y;*]
Out = {$n= \top, x = \perp, y = \perp$}
\end{lstlisting}
};

\node[draw] (4) [below right = 5 cm and 1 cm=of 2] {
\begin{lstlisting}[numbers=none]
In = {$n= \top, x = \perp, y = \perp$}
[*y = y - x;
x = 3 * (x % 4);
n = n - 1;*]
Out = {$n= \top, x = \perp, y = \perp$}
\end{lstlisting}
};

\path (1) edge node {} (2);
\path (2) edge [bend right=20pt] node {} (3);
\path (2) edge [bend right=20pt] node {} (4);
\path (4) edge [bend right=20pt] node {} (2);
\end{tikzpicture}
\caption{CFG nach Abarbeitung des ersten Blocks der Constant-Folding-Analyse}
\end{figure}

\par

\begin{figure}[H]

\centering
\begin{tikzpicture}[%
->,
shorten >=2pt,
>=stealth,
node distance=1cm,
noname/.style={%
	ellipse,
	minimum width=5em,
	minimum height=3em,
	draw
}
]

\node [draw] (1) {
\begin{lstlisting}[numbers=none]
In = {$n= \top, x = \perp, y = \perp$}
[*int x = 6;
int y = 2 * n;*]
Out = {$n= \top, x = 6, y = \top$}
\end{lstlisting}
};

\node [draw] (2) [below =of 1] {
\begin{lstlisting}[numbers=none]
In = {$n= \top, x = 6, y = \top$}
[*if (n > 0)*]
Out = {$n= \top, x = 6, y = \top$}
\end{lstlisting}
};

\node[draw] (3) [below left  = 5 cm and 1 cm=of 2] {
\begin{lstlisting}[numbers=none]
In = {$n= \top, x = 6, y = \top$}
[*return y;*]
Out = {$n= \top, x = 6, y = \top$}
\end{lstlisting}
};

\node[draw] (4) [below right  = 5 cm and 1 cm=of 2] {
\begin{lstlisting}[numbers=none]
In = {$n= \top, x = 6, y = \top$}
[*y = y - x;
x = 3 * (x % 4);
n = n - 1;*]
Out = {$n= \top, x = 6, y = \top$}
\end{lstlisting}
};

\path (1) edge node {} (2);
\path (2) edge [bend right=20pt] node {} (3);
\path (2) edge [bend right=20pt] node {} (4);
\path (4) edge [bend right=20pt] node {} (2);
\end{tikzpicture}
\caption{CFG im Fixpunkt der Constant-Folding-Analyse}
\end{figure}

\newpage

\subsection{Constant Bits}

Zu analysierender Code: \par

\begin{lstlisting}[frame=single]
int constantBits(int p) {
	int x = 8 * p;
	int y = 0;
	if (p > 0) {
		y = x % 2;
	} else {
		y = x % 4;
	}
	return x + y;
}
\end{lstlisting}

\par

\begin{figure}[H]
\centering
\begin{tikzpicture}[%
->,
shorten >=2pt,
>=stealth,
node distance=1cm,
noname/.style={%
ellipse,
minimum width=5em,
minimum height=3em,
draw
}
]
\node [draw] (1) {
\begin{lstlisting}[numbers=none]
In$_1$ = $\{p=\top, x=\perp, y=\perp \}$
[*int x = 8 * p;
int y = 0;*]
Out$_1$ = $\{p=\top, x=\perp, y=\perp \}$
\end{lstlisting}
};

\node [draw] (2) [below=of 1] {
\begin{lstlisting}[numbers=none]
In$_2$ = $\{p=\top, x=\perp, y=\perp \}$
[*if (p > 0)*]
Out$_2$ = $\{p=\top, x=\perp, y=\perp \}$
\end{lstlisting}
};

\node[draw] (3) [below left=1cm and -2cm of 2]   {
\begin{lstlisting}[numbers=none]
In$_3$ = $\{p=\top, x=\perp, y=\perp \}$
[*y = x % 2;*]
Out$_3$ = $\{p=\top, x=\perp, y=\perp \}$
\end{lstlisting}
};

\node[draw] (4) [below right=1cm and -2cm of 2]   {
\begin{lstlisting}[numbers=none]
In$_4$ = $\{p=\top, x=\perp, y=\perp \}$
[*y = x % 4;*]
Out$_4$ = $\{p=\top, x=\perp, y=\perp \}$
\end{lstlisting}
};

\node[draw] (5) [below left=1cm and -2cm of 4]   {
\begin{lstlisting}[numbers=none]
In$_5$ = $\{p=\top, x=\perp, y=\perp \}$
[*return x + y;*]
Out$_5$ = $\{p=\top, x=\perp, y=\perp \}$
\end{lstlisting}
};

\path (1) edge node {} (2);
\path (2) edge node {} (3);
\path (2) edge node {} (4);
\path (3) edge node {} (5);
\path (4) edge node {} (5);

\end{tikzpicture}
\caption{CFG im Initialzustand der Constant-Bits-Analyse}
\end{figure}

\par

\begin{figure}[H]
\centering
\begin{tikzpicture}[%
->,
shorten >=2pt,
>=stealth,
node distance=1cm,
noname/.style={%
ellipse,
minimum width=5em,
minimum height=3em,
draw
}
]
\node [draw] (1) {
\begin{lstlisting}[numbers=none]
In$_1$ = $\{p=\top, x=\perp, y=\perp \}$
[*int x = 8 * p;
int y = 0;*]
Out$_1$ = $\{p=\top, x=(\top,..., \top,0,0,0), y=(0,...,0) \}$
\end{lstlisting}
};

\node [draw] (2) [below=of 1] {
\begin{lstlisting}[numbers=none]
In$_2$ = $\{p=\top, x=(\top,..., \top,0,0,0), y=(0,...,0) \}$
[*if (p > 0)*]
Out$_2$ = $\{p=\top, x=(\top,..., \top,0,0,0), y=(0,...,0) \}$
\end{lstlisting}
};

\node[draw] (3) [below left=1cm and -4cm of 2]   {
\begin{lstlisting}[numbers=none]
In$_3$ = $\{p=\top, x=\perp, y=\perp \}$
[*y = x % 2;*]
Out$_3$ = $\{p=\top, x=\perp, y=\perp \}$
\end{lstlisting}
};

\node[draw] (4) [below right=1cm and -4cm of 2]   {
\begin{lstlisting}[numbers=none]
In$_4$ = $\{p=\top, x=\perp, y=\perp \}$
[*y = x % 4;*]
Out$_4$ = $\{p=\top, x=\perp, y=\perp \}$
\end{lstlisting}
};

\node[draw] (5) [below left=1cm and -2cm of 4]   {
\begin{lstlisting}[numbers=none]
In$_5$ = $\{p=\top, x=\perp, y=\perp \}$
[*return x + y;*]
Out$_5$ = $\{p=\top, x=\perp, y=\perp \}$
\end{lstlisting}
};

\path (1) edge node {} (2);
\path (2) edge node {} (3);
\path (2) edge node {} (4);
\path (3) edge node {} (5);
\path (4) edge node {} (5);

\end{tikzpicture}
\caption{CFG nach 2 Schritten der Constant-Bits-Analyse}
\end{figure}

\par

\begin{figure}[H]
\centering
\begin{tikzpicture}[%
->,
shorten >=2pt,
>=stealth,
node distance=1cm,
noname/.style={%
ellipse,
minimum width=5em,
minimum height=3em,
draw
}
]
\node [draw] (1) {
\begin{lstlisting}[numbers=none]
In$_1$ = $\{p=\top, x=\perp, y=\perp \}$
[*int x = 8 * p;
int y = 0;*]
Out$_1$ = $\{p=\top, x=(\top,..., \top,0,0,0), y=(0,...,0) \}$
\end{lstlisting}
};

\node [draw] (2) [below=0.8 cm of 1] {
\begin{lstlisting}[numbers=none]
In$_2$ = $\{p=\top, x=(\top,..., \top,0,0,0), y=(0,...,0) \}$
[*if (p > 0)*]
Out$_2$ = $\{p=\top, x=(\top,..., \top,0,0,0), y=(0,...,0) \}$
\end{lstlisting}
};

\node[draw] (3) [below left=0.8cm and -4cm of 2]   {
\begin{lstlisting}[numbers=none]
In$_3$ = $\{p=\top, x=(\top,..., \top,0,0,0), y=(0,...,0) \}$
[*y = x % 2;*]
Out$_3$ = $\{p=\top, x=(\top,..., \top,0,0,0), y=(0,...,0) \}$
\end{lstlisting}
};

\node[draw] (4) [below right=0.8cm and -4cm of 3]   {
\begin{lstlisting}[numbers=none]
In$_4$ = $\{p=\top, x=(\top,..., \top,0,0,0), y=(0,...,0) \}$
[*y = x % 4;*]
Out$_4$ = $\{p=\top, x=(\top,..., \top,0,0,0), y=(0,...,0) \}$
\end{lstlisting}
};

\node[draw] (5) [below left=0.8cm and -4cm of 4]   {
\begin{lstlisting}[numbers=none]
In$_5$ = $\{p=\top, x=(\top,..., \top,0,0,0), y=(0,...,0) \}$
[*return x + y;*]
Out$_5$ = $\{p=\top, x=(\top,..., \top,0,0,0), y=(0,...,0) \}$
\end{lstlisting}
};

\path (1) edge node {} (2);
\path (2) edge node {} (3);
\path (2) edge node {} (4);
\path (3) edge node {} (5);
\path (4) edge node {} (5);

\end{tikzpicture}
\caption{CFG im Fixpunkt der Constant-Bits-Analyse}
\end{figure}

\subsection{Reaching Definitions}

Zu analysierender Code: \par

\begin{lstlisting}[frame=single]
int reachingDefs(boolean c) {
	int a, b;
	a = 1;
	b = 2;
	a = 2;
	if (c) {
	  a = 3;
	} else {
	  a = 5;
	  b = 10;
	}
	return b;
}
\end{lstlisting}

\par

\begin{figure}[H]

\centering
\begin{tikzpicture}[%
->,
shorten >=2pt,
>=stealth,
node distance=1cm,
noname/.style={%
	ellipse,
	minimum width=5em,
	minimum height=3em,
	draw
}
]

\node [draw] (1) {
\begin{lstlisting}[numbers=none]
In = {}
[*int a, b;
a = 1;
b = 2;
a = 2;*]
Out = {}
\end{lstlisting}
};

\node [draw] (5) [below = 1 of 1] {
\begin{lstlisting}[numbers=none]
In = {}
[*if (c)*]
Out = {}
\end{lstlisting}
};

\node [draw] (2) [below left = 3.7 cm and 4 cm =of 5] {
\begin{lstlisting}[numbers=none]
In = {}
[*a = 3;*]
Out = {}
\end{lstlisting}
};

\node[draw] (3) [below right = 3.5 cm and 4 cm =of 5] {
\begin{lstlisting}[numbers=none]
In = {}
[*a = 5;
b = 10;*]
Out = {}
\end{lstlisting}
};

\node[draw] (4) [below = 1 of 5] {
\begin{lstlisting}[numbers=none]
In = {}
[*return b;*]
Out = {}
\end{lstlisting}
};

\path (1) edge node {} (5);
\path (5) edge node {} (2);
\path (5) edge node {} (3);
\path (3) edge node {} (4);
\path (2) edge node {} (4);
\end{tikzpicture}

\caption{CFG im Initialzustand der Reaching-Definitions-Analyse}
\end{figure}

\par

\begin{figure}[H]

\centering
\begin{tikzpicture}[%
->,
shorten >=2pt,
>=stealth,
node distance=1cm,
noname/.style={%
	ellipse,
	minimum width=5em,
	minimum height=3em,
	draw
}
]

\node [draw] (1) {
\begin{lstlisting}[numbers=none]
In = {}
[*int a, b;
a = 1;
b = 2;
a = 2;*]
Out = {b = 2, a = 2}
\end{lstlisting}
};

\node [draw] (5) [below = 1 of 1] {
\begin{lstlisting}[numbers=none]
In = {}
[*if (c)*]
Out = {}
\end{lstlisting}
};

\node [draw] (2) [below left = 3.7 cm and 4 cm =of 5] {
\begin{lstlisting}[numbers=none]
In = {}
[*a = 3;*]
Out = {}
\end{lstlisting}
};

\node[draw] (3) [below right = 3.5 cm and 4 cm =of 5] {
\begin{lstlisting}[numbers=none]
In = {}
[*a = 5;
b = 10;*]
Out = {}
\end{lstlisting}
};

\node[draw] (4) [below = 1 of 5] {
\begin{lstlisting}[numbers=none]
In = {}
[*return b;*]
Out = {}
\end{lstlisting}
};

\path (1) edge node {} (5);
\path (5) edge node {} (2);
\path (5) edge node {} (3);
\path (3) edge node {} (4);
\path (2) edge node {} (4);
\end{tikzpicture}

\caption{CFG nach dem 1. Schritt der Reaching-Definitions-Analyse}
\end{figure}

\par

\begin{figure}[H]

\centering
\begin{tikzpicture}[%
->,
shorten >=2pt,
>=stealth,
node distance=1cm,
noname/.style={%
	ellipse,
	minimum width=5em,
	minimum height=3em,
	draw
}
]

\node [draw] (1) {
\begin{lstlisting}[numbers=none]
In = {}
[*int a, b;
a = 1;
b = 2;
a = 2;*]
Out = {b = 2, a = 2}
\end{lstlisting}
};

\node [draw] (5) [below = 1 of 1] {
\begin{lstlisting}[numbers=none]
In = {b = 2, a = 2}
[*if (c)*]
Out = {b = 2, a = 2}
\end{lstlisting}
};

\node [draw] (2) [below left = 5.2 cm and 2 cm =of 5] {
\begin{lstlisting}[numbers=none]
In = {b = 2, a = 2}
[*a = 3;*]
Out = {a = 3, b = 2}
\end{lstlisting}
};

\node[draw] (3) [below right = 5 cm and 2 cm =of 5] {
\begin{lstlisting}[numbers=none]
In = {b = 2, a = 2}
[*a = 5;
b = 10;*]
Out = {a = 5, b = 10}
\end{lstlisting}
};

\node[draw] (4) [below = 3.5 of 5] {
\begin{lstlisting}[numbers=none]
In = {a = 3, b = 2, a = 5, b = 10}
[*return b;*]
Out = {a = 3, b = 2, a = 5, b = 10}
\end{lstlisting}
};

\path (1) edge node {} (5);
\path (5) edge node {} (2);
\path (5) edge node {} (3);
\path (3) edge node {} (4);
\path (2) edge node {} (4);
\end{tikzpicture}

\caption{CFG im Fixpunkt der Reaching-Definitions-Analyse}
\end{figure}

\subsection{Taint-Analyse}

Zu analysierender Code: \par

\begin{lstlisting}[frame=single]
void taintAnalysis(int z) {
	int y = 3;
	int x = foo();
	_taint(x)
	if(z > 0) {
		_clean(x);
	}
	y = x + 5;
	_sensitive(y);
}
\end{lstlisting}

\par

\begin{figure}[H]

\centering
\begin{tikzpicture}[%
->,
shorten >=2pt,
>=stealth,
node distance=1cm,
noname/.style={%
	ellipse,
	minimum width=5em,
	minimum height=3em,
	draw
}
]

\node [draw] (1) {
\begin{lstlisting}[numbers=none]
In = {taint = $\emptyset$, violation = false}
[*int y = 3;
int x = foo();
_taint(x);*]
Out = {taint = $\emptyset$, violation = false}
\end{lstlisting}
};

\node [draw] (2) [below =of 1] {
\begin{lstlisting}[numbers=none]
In = {taint = $\emptyset$, violation = false}
[*if ( z > 0)*]
Out = {taint = $\emptyset$, violation = false}
\end{lstlisting}
};

\node[draw] (3) [below left = 5.5 cm and 0 cm = of 2] {
\begin{lstlisting}[numbers=none]
In = {taint = $\emptyset$, violation = false}
[*_clean(x);*]
Out = {taint = $\emptyset$, violation = false}
\end{lstlisting}
};

\node[draw] (4) [below right = 8.5 cm and -5 cm =of 2] {
\begin{lstlisting}[numbers=none]
In = {taint = $\emptyset$, violation = false}
[*y = x + 5;
_sensitive(y);*]
Out = {taint = $\emptyset$, violation = false}
\end{lstlisting}
};

\path (1) edge node {} (2);
\path (2) edge [bend right=20pt] node {} (3);
\path (2) edge [bend left=20pt] node {} (4);
\path (3) edge [bend right=20pt] node {} (4);
\end{tikzpicture}

\caption{CFG im initialen Zustand der Taint-Analyse}
\end{figure}

\par

\begin{figure}[H]

\centering
\begin{tikzpicture}[%
->,
shorten >=2pt,
>=stealth,
node distance=1cm,
noname/.style={%
	ellipse,
	minimum width=5em,
	minimum height=3em,
	draw
}
]

\node [draw] (1) {
\begin{lstlisting}[numbers=none]
In = {taint = $\emptyset$, violation = false}
[*int y = 3;
int x = foo();
_taint(x);*]
Out = {taint = {x}, violation = false}
\end{lstlisting}
};

\node [draw] (2) [below =of 1] {
\begin{lstlisting}[numbers=none]
In = {taint = {x}, violation = false}
[*if ( z > 0)*]
Out = {taint = {x}, violation = false}
\end{lstlisting}
};

\node[draw] (3) [below left = 5.5 cm and 0 cm = of 2] {
\begin{lstlisting}[numbers=none]
In = {taint = {x}, violation = false}
[*_clean(x);*]
Out = {taint = $\emptyset$, violation = false}
\end{lstlisting}
};

\node[draw] (4) [below right = 8.5 cm and -5 cm =of 2] {
\begin{lstlisting}[numbers=none]
In = {taint = $\emptyset$, violation = false}
[*y = x + 5;
_sensitive(y);*]
Out = {taint = $\emptyset$, violation = false}
\end{lstlisting}
};

\path (1) edge node {} (2);
\path (2) edge [bend right=20pt] node {} (3);
\path (2) edge [bend left=20pt] node {} (4);
\path (3) edge [bend right=20pt] node {} (4);
\end{tikzpicture}

\caption{CFG nach Abarbeitung des dritten Blocks der Taint-Analyse}
\end{figure}

\par

\begin{figure}[H]

\centering
\begin{tikzpicture}[%
->,
shorten >=2pt,
>=stealth,
node distance=1cm,
noname/.style={%
	ellipse,
	minimum width=5em,
	minimum height=3em,
	draw
}
]

\node [draw] (1) {
\begin{lstlisting}[numbers=none]
In = {taint = $\emptyset$, violation = false}
[*int y = 3;
int x = foo();
_taint(x);*]
Out = {taint = {x}, violation = false}
\end{lstlisting}
};

\node [draw] (2) [below =of 1] {
\begin{lstlisting}[numbers=none]
In = {taint = {x}, violation = false}
[*if ( z > 0)*]
Out = {taint = {x}, violation = false}
\end{lstlisting}
};

\node[draw] (3) [below left = 5.5 cm and 0 cm = of 2] {
\begin{lstlisting}[numbers=none]
In = {taint = {x}, violation = false}
[*_clean(x);*]
Out = {taint = $\emptyset$, violation = false}
\end{lstlisting}
};

\node[draw] (4) [below right = 8.5 cm and -5 cm =of 2] {
\begin{lstlisting}[numbers=none]
In = {taint = {x}, violation = false}
[*y = x + 5;
_sensitive(y);*]
Out = {taint = {x, y}, violation = true}
\end{lstlisting}
};

\path (1) edge node {} (2);
\path (2) edge [bend right=20pt] node {} (3);
\path (2) edge [bend left=20pt] node {} (4);
\path (3) edge [bend right=20pt] node {} (4);
\end{tikzpicture}

\caption{CFG im Fixpunkt der Taint-Analyse}
\end{figure}


\subsection{Live Variables [opt]}

Zu analysierender Code: \par

\begin{lstlisting}[frame=single]
int liveVariables(int x) {
	int y = 2 * x;
	int z = 1 - x;
	if (y > 0) {
		z = y + 1;
	} else {
		z = 1 - y;
	}
	return z;
}
\end{lstlisting}

\par

\begin{figure}[H]
\centering
\begin{tikzpicture}[%
->,
shorten >=2pt,
>=stealth,
node distance=1cm,
noname/.style={%
ellipse,
minimum width=5em,
minimum height=3em,
draw
}
]
\node [draw] (1) {
\begin{lstlisting}[numbers=none]
In$_1$ = $\{ \}$
[*int y = 2 * x;
int z = 1 - x;*]
Out$_1$ = $\{ \}$
\end{lstlisting}
};

\node [draw] (2) [below=of 1] {
\begin{lstlisting}[numbers=none]
In$_2$ = $\{ \}$
[*if (y > 0)*]
Out$_2$ = $\{ \}$
\end{lstlisting}
};

\node[draw] (3) [below left=of 2]   {
\begin{lstlisting}[numbers=none]
In$_3$ = $\{ \}$
[*z = y + 1;*]
Out$_3$ = $\{ \}$
\end{lstlisting}
};

\node[draw] (4) [below right=of 2]   {
\begin{lstlisting}[numbers=none]
In$_4$ = $\{ \}$
[*z = 1 - y;*]
Out$_4$ = $\{ \}$
\end{lstlisting}
};

\node[draw] (5) [below left=of 4]   {
\begin{lstlisting}[numbers=none]
In$_5$ = $\{ \}$
[*return z;*]
Out$_5$ = $\{ \}$
\end{lstlisting}
};

\path (1) edge node {} (2);
\path (2) edge node {} (3);
\path (2) edge node {} (4);
\path (3) edge node {} (5);
\path (4) edge node {} (5);

\end{tikzpicture}
\caption{CFG im Initialzustand der Live-Variables-Analyse}
\end{figure}

\par

\begin{figure}[H]
\centering
\begin{tikzpicture}[%
->,
shorten >=2pt,
>=stealth,
node distance=1cm,
noname/.style={%
ellipse,
minimum width=5em,
minimum height=3em,
draw
}
]
\node [draw] (1) {
\begin{lstlisting}[numbers=none]
In$_1$ = $\{ \}$
[*int y = 2 * x;
int z = 1 - x;*]
Out$_1$ = $\{x \}$
\end{lstlisting}
};

\node [draw] (2) [below=of 1] {
\begin{lstlisting}[numbers=none]
In$_2$ = $\{x \}$
[*if (y > 0)*]
Out$_2$ = $\{x,y \}$
\end{lstlisting}
};

\node[draw] (3) [below left=of 2]   {
\begin{lstlisting}[numbers=none]
In$_3$ = $\{ \}$
[*z = y + 1;*]
Out$_3$ = $\{ \}$
\end{lstlisting}
};

\node[draw] (4) [below right=of 2]   {
\begin{lstlisting}[numbers=none]
In$_4$ = $\{ \}$
[*z = 1 - y;*]
Out$_4$ = $\{ \}$
\end{lstlisting}
};

\node[draw] (5) [below left=of 4]   {
\begin{lstlisting}[numbers=none]
In$_5$ = $\{ \}$
[*return z;*]
Out$_5$ = $\{ \}$
\end{lstlisting}
};

\path (1) edge node {} (2);
\path (2) edge node {} (3);
\path (2) edge node {} (4);
\path (3) edge node {} (5);
\path (4) edge node {} (5);

\end{tikzpicture}
\caption{CFG nach 2 Schritten Live-Variables-Analyse}
\end{figure}

\par

\begin{figure}[H]
\centering
\begin{tikzpicture}[%
->,
shorten >=2pt,
>=stealth,
node distance=1cm,
noname/.style={%
ellipse,
minimum width=5em,
minimum height=3em,
draw
}
]
\node [draw] (1) {
\begin{lstlisting}[numbers=none]
In$_1$ = $\{ \}$
[*int y = 2 * x;
int z = 1 - x;*]
Out$_1$ = $\{x \}$
\end{lstlisting}
};

\node [draw] (2) [below=of 1] {
\begin{lstlisting}[numbers=none]
In$_2$ = $\{x \}$
[*if (y > 0)*]
Out$_2$ = $\{x,y \}$
\end{lstlisting}
};

\node[draw] (3) [below left=of 2]   {
\begin{lstlisting}[numbers=none]
In$_3$ = $\{x,y \}$
[*z = y + 1;*]
Out$_3$ = $\{x,y \}$
\end{lstlisting}
};

\node[draw] (4) [below right=of 2]   {
\begin{lstlisting}[numbers=none]
In$_4$ = $\{x,y \}$
[*z = 1 - y;*]
Out$_4$ = $\{x,y \}$
\end{lstlisting}
};

\node[draw] (5) [below left=of 4]   {
\begin{lstlisting}[numbers=none]
In$_5$ = $\{x,y \}$
[*return z;*]
Out$_5$ = $\{x,y,z \}$
\end{lstlisting}
};

\path (1) edge node {} (2);
\path (2) edge node {} (3);
\path (2) edge node {} (4);
\path (3) edge node {} (5);
\path (4) edge node {} (5);

\end{tikzpicture}
\caption{CFG im Fixpunkt der Live-Variables-Analyse}
\end{figure}

\subsection{Definite Assignment [opt]}
Zu analysierender Code: \par

\begin{lstlisting}[frame=single]
void definiteAssignmentAnalysis(int r) {
	int x, y;
	if (r > 0){
		y = 5;
	}
	x = r + 1;
}
\end{lstlisting}

d.a. $\hat{=}$ definitely assigned \\
d.u. $\hat{=}$ definitely unassigned \\
unk. $\hat{=}$ unknown

\begin{figure}[H]

\centering
\begin{tikzpicture}[%
->,
shorten >=2pt,
>=stealth,
node distance=0.5cm,
noname/.style={%
	ellipse,
	minimum width=5em,
	minimum height=3em,
	draw
}
]

\node [draw] (1) {
\begin{lstlisting}[numbers=none]
In$_1$ = {r = unk., x = unk., y = unk.}
[*int x,y;*]
Out$_1$ = [{r = unk. x = unk., y = unk.}
\end{lstlisting}
};

\node [draw] (2) [below=of 1] {
\begin{lstlisting}[numbers=none]
In$_2$ = = {r = unk., x = unk., y = unk.}
[*if (r > 0)*]
Out$_2$ = = {r = unk., x = unk., y = unk.}
\end{lstlisting}
};

\node[draw] (3) [below left=3.7cm and -1cm=of 2]   {
\begin{lstlisting}[numbers=none]
In$_3$ = = {r = unk., x = unk., y = unk.}
[*y = 5;*]
Out$_3$ = = {r = unk., x = unk., y = unk.}
\end{lstlisting}
};

\node[draw] (4) [below=6cm and 10cm=of 2]   {
\begin{lstlisting}[numbers=none]
In$_4$ = = {r = unk., x = unk., y = unk.}
[*x = r + 1;*]
Out$_4$ = = {r = unk., x = unk., y = unk.}
\end{lstlisting}
};

\path (1) edge node {} (2);
\path (2) edge node {} (3);
\path (2) edge [bend left=60pt] node {} (4);
\path (3) edge node {} (4);
\end{tikzpicture}

\caption{CFG im Initialzustand der Definite-Assignment-Analyse}
\end{figure}

\begin{figure}[H]

\centering
\begin{tikzpicture}[%
->,
shorten >=2pt,
>=stealth,
node distance=0.5cm,
noname/.style={%
	ellipse,
	minimum width=5em,
	minimum height=3em,
	draw
}
]

\node [draw] (1) {
\begin{lstlisting}[numbers=none]
In$_1$ = {r = d.a., x = d.u., y = d.u.}
[*int x,y;*]
Out$_1$ = [{r = d.a. x = d.u., y = d.u.}
\end{lstlisting}
};

\node [draw] (2) [below=of 1] {
\begin{lstlisting}[numbers=none]
In$_2$ = = {r = unk., x = unk., y = unk.}
[*if (r > 0)*]
Out$_2$ = = {r = unk., x = unk., y = unk.}
\end{lstlisting}
};

\node[draw] (3) [below left=3.7cm and -1cm=of 2]   {
\begin{lstlisting}[numbers=none]
In$_3$ = = {r = unk., x = unk., y = unk.}
[*y = 5;*]
Out$_3$ = = {r = unk., x = unk., y = unk.}
\end{lstlisting}
};

\node[draw] (4) [below=6cm and 10cm=of 2]   {
\begin{lstlisting}[numbers=none]
In$_4$ = = {r = unk., x = unk., y = unk.}
[*x = r + 1;*]
Out$_4$ = = {r = unk., x = unk., y = unk.}
\end{lstlisting}
};

\path (1) edge node {} (2);
\path (2) edge node {} (3);
\path (2) edge [bend left=60pt] node {} (4);
\path (3) edge node {} (4);
\end{tikzpicture}

\caption{CFG nach einem Schritt der Definite-Assignment-Analyse}
\end{figure}

\begin{figure}[H]

\centering
\begin{tikzpicture}[%
->,
shorten >=2pt,
>=stealth,
node distance=0.5cm,
noname/.style={%
	ellipse,
	minimum width=5em,
	minimum height=3em,
	draw
}
]

\node [draw] (1) {
\begin{lstlisting}[numbers=none]
In$_1$ = {r = d.a., x = d.u., y = d.u.}
[*int x,y;*]
Out$_1$ = [{r = d.a. x = d.u., y = d.u.}
\end{lstlisting}
};

\node [draw] (2) [below=of 1] {
\begin{lstlisting}[numbers=none]
In$_2$ = = {r = d.a., x = d.u., y = d.u.}
[*if (r > 0)*]
Out$_2$ = = {r = d.a., x = d.u., y = d.u.}
\end{lstlisting}
};

\node[draw] (3) [below left=3.7cm and -1cm=of 2]   {
\begin{lstlisting}[numbers=none]
In$_3$ = = {r = d.a., x = d.u., y = d.u.}
[*y = 5;*]
Out$_3$ = = {r = d.a., x = d.a., y = d.u.}
\end{lstlisting}
};

\node[draw] (4) [below=6cm and 10cm=of 2]   {
\begin{lstlisting}[numbers=none]
In$_4$ = = {r = d.a., x = d.u., y = unk.}
[*x = r + 1;*]
Out$_4$ = = {r = d.a., x = d.a., y = unk.}
\end{lstlisting}
};

\path (1) edge node {} (2);
\path (2) edge node {} (3);
\path (2) edge [bend left=60pt] node {} (4);
\path (3) edge node {} (4);
\end{tikzpicture}

\caption{CFG im Fixpunkt der Definite-Assignment-Analyse}
\end{figure}

\subsection{Available Expressions [opt]}
Zu analysierender Code: \par

\begin{lstlisting}[frame=single]
int availableExpressions(int x, int y) {
	int s,t;
	if((x+1)*(x+1)==y){
		s=x+y;
	}
	if(x*x+2*x+1!=y){
		t=x+y;
	}
	return x+y;
}
\end{lstlisting}

\par

\begin{figure}[H]

\centering
\begin{tikzpicture}[%
->,
shorten >=2pt,
>=stealth,
node distance=0.5cm,
noname/.style={%
	ellipse,
	minimum width=5em,
	minimum height=3em,
	draw
}
]

\node [draw] (1) {
\begin{lstlisting}[numbers=none]
In$_1$ = {}
[*int s,t;*]
Out$_1$ = {}
\end{lstlisting}
};

\node [draw] (2) [below=of 1] {
\begin{lstlisting}[numbers=none]
In$_2$ = {}
[*if ((x+1) * (x+1) == y)*]
Out$_2$ = {}
\end{lstlisting}
};

\node[draw] (3) [below left=3.9cm and 0 cm=of 2]   {
\begin{lstlisting}[numbers=none]
In$_3$ = {}
[*s = x+y;*]
Out$_3$ = {}
\end{lstlisting}
};

\node[draw] (4) [below=6.3cm and 0 cm=of 2]   {
\begin{lstlisting}[numbers=none]
In$_4$ = {}
[*if (x*x + 2*x + 1 != y)*]
Out$_4$ = {}
\end{lstlisting}
};

\node[draw] (5) [below left=8.7cm and 0cm=of 4]   {
\begin{lstlisting}[numbers=none]
In$_5$ = {}
[*t = x+y;*]
Out$_5$ = {}
\end{lstlisting}
};

\node[draw] (6) [below=11.1cm and 0 cm=of 2]   {
\begin{lstlisting}[numbers=none]
In$_6$ = {}
[*return x+y;*]
Out$_6$ = {}
\end{lstlisting}
};

\path (1) edge node {} (2);
\path (2) edge [bend right=15pt]node {} (3);
\path (2) edge [bend left=25pt] node {} (4);
\path (3) edge [bend right=15pt]node {} (4);
\path (4) edge [bend right=15pt]node {} (5);
\path (5) edge [bend right=15pt]node {} (6);
\path (4) edge [bend left=25pt] node {} (6);
\end{tikzpicture}

\caption{CFG im Initialzustand der Available-Expression-Analyse}
\end{figure}

\par

\begin{figure}[H]

\centering
\begin{tikzpicture}[%
->,
shorten >=2pt,
>=stealth,
node distance=0.5cm,
noname/.style={%
	ellipse,
	minimum width=5em,
	minimum height=3em,
	draw
}
]

\node [draw] (1) {
\begin{lstlisting}[numbers=none]
In$_1$ = {$x,$ $y$}
[*int s,t;*]
Out$_1$ = In$_1$
\end{lstlisting}
};

\node [draw] (2) [below=of 1] {
\begin{lstlisting}[numbers=none]
In$_2$ = Out$_1$
[*if ((x+1) * (x+1) == y)*]
Out$_2$ = In$_2$ $\cup$ {$x+1,$ $(x+1)*(x+1),$ $(x+1)*(x+1)==y$}
\end{lstlisting}
};

\node[draw] (3) [below left=3.9cm and 0 cm=of 2]   {
\begin{lstlisting}[numbers=none]
In$_3$ = {}
[*s = x+y;*]
Out$_3$ = {}
\end{lstlisting}
};

\node[draw] (4) [below=6.3cm and 0 cm=of 2]   {
\begin{lstlisting}[numbers=none]
In$_4$ = {}
[*if (x*x + 2*x + 1 != y)*]
Out$_4$ = {}
\end{lstlisting}
};

\node[draw] (5) [below left=8.7cm and 0cm=of 4]   {
\begin{lstlisting}[numbers=none]
In$_5$ = {}
[*t = x+y;*]
Out$_5$ = {}
\end{lstlisting}
};

\node[draw] (6) [below=11.1cm and 0 cm=of 2]   {
\begin{lstlisting}[numbers=none]
In$_6$ = {}
[*return x+y;*]
Out$_6$ = {}
\end{lstlisting}
};

\path (1) edge node {} (2);
\path (2) edge [bend right=15pt]node {} (3);
\path (2) edge [bend left=25pt] node {} (4);
\path (3) edge [bend right=15pt]node {} (4);
\path (4) edge [bend right=15pt]node {} (5);
\path (5) edge [bend right=15pt]node {} (6);
\path (4) edge [bend left=25pt] node {} (6);
\end{tikzpicture}

\caption{CFG nach 2 Schritten der Available-Expression-Analyse}
\end{figure}

\par

\begin{figure}[H]

\centering
\begin{tikzpicture}[%
->,
shorten >=2pt,
>=stealth,
node distance=0.5cm,
noname/.style={%
	ellipse,
	minimum width=5em,
	minimum height=3em,
	draw
}
]

\node [draw] (1) {
\begin{lstlisting}[numbers=none]
In$_1$ = {$x,$ $y$}
[*int s,t;*]
Out$_1$ = In$_1$
\end{lstlisting}
};

\node [draw] (2) [below=of 1] {
\begin{lstlisting}[numbers=none]
In$_2$ = Out$_1$
[*if ((x+1) * (x+1) == y)*]
Out$_2$ = In$_2$ $\cup$ {$x+1,$ $(x+1)*(x+1),$ $(x+1)*(x+1)==y$}
\end{lstlisting}
};

\node[draw] (3) [below left=3.9cm and 0 cm=of 2]   {
\begin{lstlisting}[numbers=none]
In$_3$ = Out$_2$
[*s = x+y;*]
Out$_3$ = In$_3$ $\cup$ {$x+y,$ $s$}
\end{lstlisting}
};

\node[draw] (4) [below=6.3cm and 0 cm=of 2]   {
\begin{lstlisting}[numbers=none]
In$_4$ = Out$_2$ $\cap$ Out$_3$ = Out$_2$
[*if (x*x + 2*x + 1 != y)*]
Out$_4$ = In$_4$ $\cup$ {$x*x,$ $2*x,$ $x*x+2*x,$ $x*x+2*x+1,$ $x*x+2*x+1!=y$}
\end{lstlisting}
};

\node[draw] (5) [below left=8.7cm and 0cm=of 4]   {
\begin{lstlisting}[numbers=none]
In$_5$ = Out$_4$
[*t = x+y;*]
Out$_5$ = In$_5$ $\cup$ {$x+y,$ $t$}
\end{lstlisting}
};

\node[draw] (6) [below=11.1cm and 0 cm=of 2]   {
\begin{lstlisting}[numbers=none]
In$_6$ = Out$_4$ $\cap$ Out$_5$ = Out$_4$
[*return x+y;*]
Out$_6$ = In$_6$ $\cup$ {$x+y$}
\end{lstlisting}
};

\path (1) edge node {} (2);
\path (2) edge [bend right=15pt]node {} (3);
\path (2) edge [bend left=25pt] node {} (4);
\path (3) edge [bend right=15pt]node {} (4);
\path (4) edge [bend right=15pt]node {} (5);
\path (5) edge [bend right=15pt]node {} (6);
\path (4) edge [bend left=25pt] node {} (6);
\end{tikzpicture}

\caption{CFG im Fixpunkt der Available-Expression-Analyse}
\end{figure}
