1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
|
\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}
|
