From 839764bd955d2bddedb4a38ab1d4d92c797c56b9 Mon Sep 17 00:00:00 2001
From: Carlo Zancanaro <carlo@pc-4w14-0.cs.usyd.edu.au>
Date: Tue, 27 Nov 2012 18:20:06 +1100
Subject: Thesis and performance testing related stuff.

---
 tex/thesis/implementation/implementation.tex | 85 +++++++++++++++++++++++++++-
 1 file changed, 83 insertions(+), 2 deletions(-)

(limited to 'tex/thesis/implementation/implementation.tex')

diff --git a/tex/thesis/implementation/implementation.tex b/tex/thesis/implementation/implementation.tex
index 7e432f8..02f2180 100644
--- a/tex/thesis/implementation/implementation.tex
+++ b/tex/thesis/implementation/implementation.tex
@@ -13,18 +13,99 @@ develop it in C++ for two major reasons:
   obvious choice of language.
 \end{itemize}
 
+
+\section{Solver}
+
+The solver is a straightforward implementation of the algorithm
+presented in Chapter \ref{chap:contribution}. The primary difference
+is the use of objects instead of higher-order functions, as C++'s
+support for higher-order functions was insufficient for our purposes.
+
 The solver was developed using only the STL for the core of the
 solver. A front-end was developed using the ANTLR parser generator
 \cite{antlr} to test the solver separately to the LLVM/Clang
 integration.
 
-\section{Solver}
+
+\subsection{Chain}
+
+
+
+
+\subsection{Cycle}
+
+
+
+\subsection{Dense}
+
 
 
 \section{LLVM/Clang}
 
+We implemented our analysis as a Clang Static Analysis pass, building
+off the Clang Static Analysis framework~\cite{clang-analysis}. Using
+the infrastructure of the Clang project provided us with a CFG without
+any extra work parsing, or otherwise handling, C code itself.
+
+Figure \ref{fig:clang-diagram} gives a very high-level idea of the
+structure of our analysis pass and how it interfaces with other
+components. The Clang framework provides the Zone analysis with a
+Control Flow Graph. This CFG is then translated to a system of
+monotonic, expansive equations. The DSI algorithm is designed to solve
+these equation systems, and so we invoke our solver to provide us with
+a solution. This solution identifies the bounds for variables at
+different points in the program.
 
+\begin{figure}[tbphH]
+  \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node
+      distance=4cm,main node/.style={rectangle,draw,minimum
+        height=2cm,minimum width=3cm}]
+    
+    %\node[main node] (clang) {Clang Framework};
+    \node[main node] (clang-analysis) {Clang Static Analysis Framework};
+    \node[main node,fill=red!60] (eqns) [below of=clang-analysis]
+         {Zone analysis};
+    \node[main node] (dsi) [below of=eqns] {DSI};
+    \node (reality) [node distance=5cm,right of=eqns] {};
 
-\subsection{Chain construction}
+    \path []
+    %(clang) edge[bend right] node[anchor=east] {CFG} (clang-analysis)
+    (clang-analysis) edge[bend right] node[anchor=east] {CFG} (eqns)
+    (eqns) edge[bend right] node[anchor=east] {Equation System} (dsi)
+    (dsi) edge[bend right] node[anchor=west] {Solution} (eqns)
+    (eqns) edge node[anchor=north] {Variable bounds} (reality)
+    %(eqns) edge[bend right] node[anchor=west] {Variable bounds} (clang-analysis)
+    %(clang-analysis) edge[bend right] node[anchor=west] {Errors/warnings} (clang)
+    ;
 
+  \end{tikzpicture}
+  \caption{High-level diagram of our analysis pass}
+  \label{fig:clang-diagram}
+\end{figure}
+
+
+\pagebreak
+\subsection{Chain}
 \lstinputlisting{implementation/experiments/chain.c}
+
+\pagebreak
+\subsection{Counter}
+\lstinputlisting{implementation/experiments/counter.c}
+
+\lstinputlisting{implementation/experiments/backwards_counter.c}
+
+\pagebreak
+\subsection{Nested Loops}
+\lstinputlisting{implementation/experiments/nested.c}
+
+\pagebreak
+\subsection{Double counting}
+\lstinputlisting{implementation/experiments/example.c}
+
+\pagebreak
+\subsection{Fibonacci}
+\lstinputlisting{implementation/experiments/fib.c}
+
+\pagebreak
+\subsection{Unreachable}
+\lstinputlisting{implementation/experiments/irreducible.c}
-- 
cgit v1.2.3