\chapter{Implementation} \label{chap:implementation}

Our implementation of the Demand Driven Strategy Improvement algorithm
presented in Chapter \ref{chap:contribution} is in C++. We chose to
develop it in C++ for two major reasons:
\begin{itemize}
\item
  C++ provides a programmer with fine-grained control of resources, in
  particular memory.
\item
  The LLVM/Clang framework is written in C++. As integration with
  LLVM/Clang was always a major goal for this project, C++ was the
  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.


\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] {};

    \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}